Search

In recent years we have increasingly seen the movement for the retail industry to move their operations online. Along the process, it has created brand new patterns for the fulfillment service, and the logistics service providers serving these retailers have no choice but to adapt. The most challenging issues faced by all logistics service providers are the highly fluctuating demands and the shortening response times. All these challenges imply that maintaining a fixed fleet will either be too costly or insufficient. One potential solution is to tap into the crowdsourced workforce. However, existing industry practices of relying on human planners or worker's self-planning have been shown to be inefficient and laborious. In this paper, we introduce a centralized planning model for the crowdsourced logistics delivery paradigm, considering individual worker's spatio-temporal preferences. Considering worker's spatio-temporal preferences is important for the planner as it could significantly improve crowdsourced worker's productivity. Our major contributions are in the formulation of the problem as a mixed-integer program and the proposal of an efficient algorithm that is based on the column generation and the Lagrangian relaxation frameworks. Such a hybrid approach allows us to overcome the difficulty encountered separately by the classical column generation and Lagrangian relaxation approaches. By using a series of real-world-inspired numerical instances, we have demonstrated the effectiveness of our approach against classical column generation and Lagrangian relaxation approaches, and a decentralized, agent-centric greedy approach. Our proposed hybrid approach is scalable to large problem instances, with reasonable solution quality, and achieves better allocation fairness.

On-demand transportation services have been developing in an irresistible trend since their first launch in public. These services not only transform the urban mobility landscape, but also profoundly change individuals’ travel behavior and demand for cars. In this paper, we propose an integrated model structure which integrates empirical analysis into a discrete choice based analytical framework to investigate a heterogenous population’s choices on transportation mode and car ownership with the presence of ride-hailing. Distinguished from traditional discrete choice models where individuals’ choices are only affected by exogenous variables and are independent of other individuals’ choices, our model extends to capture the endogeneity of supply demand imbalance between ride-hailing service providers and users. Through equilibrium searching and counterfactual analysis, we further quantify the magnitude of impacts of platform operations and government policies on car demand, usage and traffic conditions. The structure of the model and managerial insights are explained in detail.

We examine the impact of an anticipated income shock on Singaporean taxi labor supply. This income shock is due to a government provision allowing employees to withdraw part of their pension savings at the age of 55. The results show that salary income, number of trips, total hours worked, and active hours worked decrease after drivers reach age 55 by 3.5%, 3.2%, 1.6%, and 3.1%, respectively. The impact on labor supply is more marked right after drivers reach age 55, and the response is stronger among those with higher education or with lower salary income. Moreover, we find that the anticipated income shock decreases the extensive margin by 5.79%.

We study the role of ride-hailing surge factors on the allocative efficiency of taxis by combining a reduced form estimation with structural analyses using machine-learning-based demand predictions. We estimate an upper-bound of the cross-price elasticity of taxi bookings to surge factors of only 0.26, but incorporating surge factors into a demand-prediction model improves the out-of-sample accuracy by 12-15%. Our structural analyses based on a driver guidance system finds the improved accuracy reduces drivers' vacant roaming times by 9.4% and increases average trips per taxi by 2.3%, suggesting the price information is valuable across platforms, even if elasticities are low.

Mobile crowd-sourcing can become as a strategy to perform time-sensitive urban tasks (such as municipal monitoring and last mile logistics) by effectively coordinating smartphone users. The success of the mobile crowd-sourcing platform depends mainly on its effectiveness in engaging crowd-workers, and recent studies have shown that compared to the pull-based approach, which relies on crowd-workers to browse and commit to tasks they would want to perform, the push-based approach can take into consideration of worker's daily routine, and generate highly effective recommendations. As a result, workers waste less time on detours, plan more in advance, and require much less planning effort. However, the push-based systems are not without drawbacks. The major concern is the potential privacy invasion that could result from the disclosure of individual's mobility traces to the crowd-sourcing platform. In this paper, we first demonstrate specific threats of continuous sharing of users locations in such push-based crowd-sourcing platforms. We then propose a simple yet effective location perturbation technique that obfuscates certain user locations to achieve privacy guarantees while not affecting the quality of the recommendations the system generates.We use the mobility traces data we obtained from our urban campus to show the trade-offs between privacy guarantees and the quality of the recommendations associated with the proposed solution. We show that obfuscating even 75% of the individual trajectories will affect the user to make another extra 1.8 minutes of detour while gaining 62.5% more uncertainty of his location traces.

This article introduces a class of finite-horizon dynamic optimization problems that are called multi-action stochastic Dynamic Programs (DPs). Their distinguishing feature is that the decision in each state is a multi-dimensional vector. These problems can in principle be solved using Bellman’s backward recursion. However, the complexity of this procedure grows exponentially in the dimension of the decision vectors. This is called the curse of action space dimensionality. To overcome this computational challenge, an approximation algorithm is proposed that is rooted in the game-theoretic paradigm of Sampled Fictitious Play (SFP). SFP solves a sequence of DPs with a one-dimensional action space that are exponentially smaller than the original multi-action stochastic DP. In particular, the computational effort in a fixed number of SFP iterations is linear in the dimension of the decision vectors. It is shown that the sequence of SFP iterates converges to a local optimum, and a numerical case study in manuf...

In this paper, we formulate and study the Multi-agent Orienteering Problem with Time-dependent Capacity Constraints (MOPTCC). MOPTCC is similar to the classical orienteering problem at the single-agent level: given a limited time budget, an agent travels around the network and collects rewards by visiting different nodes, with the objective of maximizing the sum of his collected rewards. The most important feature we introduce in MOPTCC is the inclusion of multiple competing and interacting agents. All agents in MOPTCC are assumed to be self-interested, and they interact with each other when arrive at the same nodes simultaneously. As all nodes are capacitated, if a particular node receives more agents than its capacity, all agents at that node will be made to wait and agents suffer collectively as a result (in terms of extra time needed for queueing). Due to the decentralized nature of the problem, MOPTCC cannot be solved in a centralized manner; instead, we need to seek out equilibrium solutions; and if this is not possible, at least approximated equilibrium solutions. The major contribution of this paper is the formulation of the problem, and our first attempt in identifying an efficient and effective equilibrium-seeking procedure for MOPTCC.

Diffusion processes have increasingly been used to represent flow of ideas, traffic and diseases in networks. Learning and controlling the diffusion dynamics through management actions has been studied extensively in the context of independent cascade models, where diffusion on outgoing edges from a node are independent of each other. Our work, in contrast, addresses (a) learning diffusion dynamics parameters and (b) taking management actions to alter the diffusion dynamics to achieve a desired outcome in dependent cascade models. A key characteristic of such dependent cascade models is the flow preservation at all nodes in the network. For example, traffic and people flow is preserved at each network node. As a case study, we address learning visitor mobility pattern at a theme park based on observed historical wait times at individual attractions, and use the learned model to plan management actions that reduce wait time at attractions. We test on real-world data from a theme park in Singapore and show that our learning approach can achieve an accuracy close to 80% for popular attractions, and the decision support algorithm can provide about 10-20% reduction in wait time.

In this paper, we introduce a variant of the density peaks clustering (DPC) approach for discovering demand hot spots from a low-frequency, low-quality taxi fleet operational dataset. From the literature, the DPC approach mainly uses density peaks as features to discover potential cluster centers, and this requires distances between all pairs of data points to be calculated. This implies that the DPC approach can only be applied to cases with relatively small numbers of data points. For the domain of urban taxi operations that we are interested in, we could have millions of demand points per day, and calculating all-pair distances between all demand points would be practically impossible, thus making DPC approach not applicable. To address this issue, we project all points to a density image and execute our variant of the DPC algorithm on the processed image. Experiment results show that our proposed DPC variant could get similar results as original DPC, yet with much shorter execution time and lower memory consumption. By running our DPC variant on a real-world dataset collected in Singapore, we show that there are indeed recurrent demand hot spots within the central business district that are not covered by the current taxi stand design. Our approach could be of use to both taxi fleet operator and traffic planners in guiding drivers and setting up taxi stands.

The annual trading agent competition offers agent designers a forum for evaluating programmed trading techniques in a challenging market scenario. TAC aims to spur research by enabling researchers to compare techniques on a common problem and build on each other's ideas. A fixed set of assumptions and environment settings facilitates communication of methods and results. As a multiyear event, TAC lets researchers observe trading agents' progress over time, in effect accelerating the evolution of an adapted population of traders. Given all the participant effort invested, it is incumbent on us to learn as much from the experience as possible. After three years of TAC, we're ready to examine there we stand. To do this, we used data from actual TAC tournaments and some post-competition experimentation. We based our analysis almost entirely on outcomes (profits and allocations), with very little direct accounting for specific agent techniques.

We use a unique dataset from a Singaporean taxi fleet consisting of 3,250 drivers with 23 months of daily work routines to test if taxi drivers exhibit learning by doing (LBD). We find strong evidence of LBD. Next, we document the channels of learning: drivers learn through temporal (when) and locational (where) and technology (booking) optimization, and we further show that drivers with consistent wage growth utilize the locational and technological channels more than others. We also discuss the implication of our findings for taxi markets experiencing a rise in use of technology (i.e. booking systems based on applications like Uber), which has recently drawn the interest of policymakers.

Unprecedented pace of urbanization and rising income levels have fueled the growth of car ownership in almost all newly formed mega cities. Such growth has congested the limited road space and significantly affected the quality of life in these mega cities. Convincing residents to give up their cars and use public transport is the most effective way in reducing congestion, however, even with sufficient public transport capacity, the lack of last-mile (from the transport hub to the destination) travel services is the major deterrent for the adoption of public transport. Due to the dynamic nature of such travel demands, fixed-size fleets will not be a cost-effective approach in addressing last-mile demands. Instead, we propose a dynamic, incentive-based mechanism that enables taxi ride-sharing for satisfying last-mile travel demands. On the demand side, travelers would register their last-mile travel demands in real-time, and they are expected to receive ride arrangements before they reach the hub, on the supply side, depending on the real-time demands, proper incentives will be computed and provided to taxi drivers willing to commit to the last-mile service. Multiple travelers will be clustered into groups according to their destinations, and travelers belonging to the same group will be assigned to a taxi, while each of them paying fares considering their destinations and also their orders in reaching destinations. In this paper, we provide mathematical formulations for demand clustering and fare distribution. If the model returns a solution, it is guaranteed to be implement able. For cases where it is not possible to satisfy all demands despite having enough capacity, we propose a two-phase approach that identifies the maximal subset of riders that can be feasibly served. Finally, we use a series of numerical examples to demonstrate the effectiveness of our approach.

Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence on the overall solution quality, then we can take advantage of randomization and the resulting statistical concentration to show that each agent can safely plan based only on the average behavior of the other agents. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs, (b) a proof of convergence of our algorithm to a near-optimal solution. We demonstrate the scalability of our approach with a large-scale illustrative theme park crowd management problem.

On May 6, 2010, the US equity markets experienced a brief but highly unusual drop in prices across a number of stocks and indices. The Dow Jones Industrial Average (DJIA) fell by approximately 9% in a matter of minutes, and several stocks were traded down sharply before recovering a short time later. Earlier research by Lee, Cheng and Koh (2010) identified the conditions under which a “flash crash” can be triggered by systematic traders running highly similar trading strategies, especially when they are “crowding out” other liquidity providers in the market. The authors contend that the events of May 6, 2010 exhibit patterns consistent with the type of “flash crash” observed in their earlier study (2010). While some commentators assigned blame to high-frequency trading, our analysis was unable to identify a direct link to high-frequency trading per se, but rather the domination of market activities by trading strategies that are responding to the same set of market variables in similar ways, as well as various pre-existing market micro-structural safety mechanisms with unintended consequences when triggered simultaneously. The consequent lack of market participants interested in the “other side” of their trades may result in a significant liquidity withdrawal during extreme market movements. This paper describes the results of 9 different simulations created by using a large-scale computer model to reconstruct the critical elements of the market events of May 6, 2010. The resulting price distribution provides a reasonable resemblance to the descriptive statistics of the second-by-second prices of S&P500 e-Mini futures from 14:30 to 15:00 on May 6, 2010. There are no a priori assumptions made on asset price distributions, and our description of market dynamics is purely based on the structure of the market and the key types of market participants involved. This type of simulation avoids “over-fitting” historical data, and can therefore provide regulators with deeper insights on the possible drivers of the “flash crash”, as well as what type of policy responses may work or may not work under comparable market circumstances in the future. Our results also lead to a natural question for policy markers: If certain prescriptive measures such as position limits have a low probability of meeting its policy objectives on a day like May 6, will there be any other more effective counter measures without unintended consequences?

We construct an agent-based model to study the interplay between extreme price shocks and illiquidity in the presence of systematic traders known as trend followers. The agent-based approach is particularly attractive in modeling commodity markets because the approach allows for the explicit modeling of production, capacities, and storage constraints. Our study begins by using the price stream from a market simulation involving human participants and studies the behavior of various trend-following strategies, assuming initially that their participation will not impact the market. We notice an incremental deterioration in strategy performance as and when strategies deviate further and further from the theoretical strategy of lookback straddles (Fung and Hsieh 2001), due to the negative impacts of transaction cost and imperfect execution. Next, the trend followers are allowed to participate in the market, trading against “uninformed” computer traders making randomized bids and offers. We notice that market prices begin to break down as the percentage of trend followers in the market reaches 80%. In addition, in a market dominated by “smart traders”, it becomes increasingly difficult for any of them to generate profits using what is supposed to be a “long gamma” strategy. After all, trading is a zero-sum game: It is not feasible for any “long gamma” trader to generate a consistent profit unless someone else is willing to be on the other side of his/her trades. In any such market dominated by “smart traders” with low liquidity and extreme price instability, one proposed solution (as proposed earlier by the U.S. Commodity Futures Trading Commission) is to control position size limits, by either decreasing them (in the original proposal) or increasing them (for completeness in our analysis). Based on our simulation results, we have found no evidence supporting that such a solution will be effective; in fact, doing so will only lead to erratic price behavior as well as a variety of practical issues when imposing such changes to position size limits. An alternative proposal is to intervene in the market direct/indirectly, such as by using a market maker to inject/reduce liquidity. Our simulation results show evidence that injecting and reducing liquidity by the market maker can both be effective. However, a market maker can accumulate a large negative P&L by buying in a one-sided, falling market in which it is the only bidder, or vice versa. Therefore, in practice, no market maker may volunteer to participate in any such “market rescue” efforts unless governments are willing to underwrite some of its large potential losses. In short, direct/indirect intervention by controlling liquidity is not a panacea, and there are practical limits to its effectiveness.

We consider the problem of resource allocation and scheduling where information and decisions are decentralized, and our goal is to propose a market mechanism that allows resources from a central resource pool to be allocated to distributed decision makers (agents) that seek to optimize their respective scheduling goals. We propose a generic combinatorial auction mechanism that allows agents to competitively bid for the resources needed in a multi-period setting, regardless of the respective scheduling problem faced by the agent, and show how agents can design optimal bidding strategies to respond to price adjustment strategies from the auctioneer. We apply our approach to handle real-time large-scale dynamic resource coordination in a mega-scale container terminal.

This paper describes our current work in designing an experimental gaming platform for simulating the trading of grid resources. The open platform allows researchers in grid economics to experiment with different market structures and pricing models. We would be using a design science approach in the implementation. Key design considerations and an overview of the functional design of the platform are presented and discussed. © CGU 2007.

TAC-02 was the third in a series of Trading Agent Competition events fostering research in automating trading strategies by showcasing alternate approaches in an open-invitation market game. TAC presents a challenging travel-shopping scenario where agents must satisfy client preferences for complementary and substitutable goods by interacting through a variety of market types. Michigan's entry, Walverine, attempts to bid optimally based on a competitive analysis of the TAC travel economy. Walverine's approach embodies several techniques not previously employed in TAC: (1) price prediction based on competitive equilibrium analysis, (2) hedged optimization with respect to a model of outlier prices, (3) optimal bidding based on a decision-theoretic calculation of bid actions, and (4) reinforcement learning for CDA trading strategies. Each of these is potentially applicable in a broad class of trading environments.

In modern production systems, it is critical to perform maintenance, calibration, installation, and upgrade tasks during planned downtime. Otherwise, the systems become unreliable and new product introductions are delayed. For reasons of safety, testing, and access, task performance often requires the vicinity of impacted equipment to be left in a specific “end state” when production halts. Therefore, planning the shutdown of a production system to balance production goals against enabling non-production tasks yields a challenging optimization problem. In this paper, we propose a mathematical formulation of this problem and a dynamic programming approach that e ciently finds optimal shutdown policies for deterministic serial production lines. An event-triggered re-optimization procedure that is based on the proposed deterministic dynamic programming approach is also introduced for handling uncertainties in the production line for the stochastic case. We demonstrate numerically that in these cases with random breakdowns and repairs, the re-optimization procedure is e cient and even obtains results that are optimal or nearly optimal.