25 February 2022 in Transportation Research Part C: Emerging Technologies
27 October 2021 in Transportation Research Part C: Emerging Technologies
1 January 2024 in Transportation Science
With the recent boom of the gig economy, urban delivery systems have experienced substantial demand growth. In such systems, orders are delivered to customers from local distribution points respecting a delivery time promise. An important example is a restaurant meal delivery system, where delivery times are expected to be minutes after an order is placed. The system serves orders by making use of couriers that continuously perform pickups and deliveries. Operating such a rapid delivery system is very challenging, primarily because of the high service expectations and the considerable uncertainty in both demand and delivery capacity. Delivery providers typically plan courier shifts for an operating period based on a demand forecast. However, because of the high demand volatility, it may at times during the operating period be necessary to adjust and dynamically add couriers. We study the problem of dynamically adding courier capacity in a rapid delivery system and propose a deep reinforcement-learning approach to obtain a policy that balances the cost of adding couriers and the cost-of-service quality degradation because of insufficient delivery capacity. Specifically, we seek to ensure that a high fraction of orders is delivered on time with a small number of courier hours. A computational study in the meal delivery space shows that a learned policy outperforms policies representing current practice and demonstrates the potential of deep learning for solving operational problems in highly stochastic logistic settings. History: This paper has been accepted for the Transportation Science Special Issue on Machine-Learning Methods and Applications in Large-Scale Route Planning Problems. Funding: This work was supported by Agencia Nacional de Investigación y Desarrollo [72180404]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2022.0042 .
16 August 2024 in Transportation Science
In the age of e-commerce, logistics companies often operate within extensive road networks without accurate knowledge of travel times for their specific fleet of vehicles. Moreover, millions of dollars are spent on routing services that fail to accurately capture the unique characteristics of the drivers and vehicles of the companies. In this work, we address the challenge faced by a logistic operator with limited travel time information, aiming to find the optimal expected shortest path between origin-destination pairs. We model this problem as an online shortest path problem, common to many last-mile routing settings; given a graph whose arcs’ travel times are stochastic and follow an unknown distribution, the objective is to find a vehicle route of minimum travel time from an origin to a destination. The planner progressively collects travel condition data as drivers complete their routes. Inspired by the combinatorial multiarmed bandit and kriging literature, we propose three methods with distinct features to effectively learn the optimal shortest path, highlighting the practical advantages of incorporating spatial correlation in the learning process. Our approach balances exploration (improving estimates for unexplored arcs) and exploitation (executing the minimum expected time path) using the Thompson sampling algorithm. In each iteration, our algorithm executes the path that minimizes the expected travel time based on data from a posterior distribution of the speeds of the arcs. We conduct a computational study comprising two settings: a set of four artificial instances and a real-life case study. The case study uses empirical data of taxis in the 17-km-radius area of the center of Beijing, encompassing Beijing’s “5th Ring Road.” In both settings, our algorithms demonstrate efficient and effective balancing of the exploration-exploitation trade-off.
27 May 2024 in EURO Journal on Transportation and Logistics
24 March 2026 in SSRN Electronic Journal
Preventive security is a critical social priority for communities, and so effective resource deployment is key. This paper concerns the optimal design of patrol areas called police districts---namely, the problem of police districting, where an urban region is divided according to various attributes such as: equitable distribution of workload; district compactness; and connectivity between units within districts. In this study, we present a new, high-resolution formulation considering street-segment units. Much of the literature on districting focuses on coarser, area-based indicators (\eg neighbourhoods), but the variance in police workload on a street-by-street basis suggest substantial benefits from a finer-grained approach. However, our high resolution model can present a major computational challenge to state-of-the-art optimization algorithms. Consequently we develop a novel method to solve the problem, formulating it as a mixed integer linear programming model that divides the urban region into districts while achieving a balanced distribution of cumulative crime levels across these districts. While our model generates balanced districts, for the sake of computational tractability it does not enforce the desirable attributes of district compactness and connectivity. Thus we develop a three-phase heuristic to refine the solution from the mixed-integer programming model. For our case study, we present the case of the police department of Antofagasta, Chile, consisting of over 10,000 street segments.