Skip to content
Article

Local Area Subset Row Inequalities for Efficient Exact Vehicle Routing

 
Download PDF  (1.44 MB)
Publication:  arXiv e-prints (2022): arXiv-2209
Publication Date: 2022
Summary:
In this research we consider an approach for improving the efficiency and tightness of column generation (CG) methods for solving vehicle routing problems. This work builds upon recent work on Local Area (LA) routes. LA routes rely on pre-computing (prior to any call to pricing during CG) the lowest cost elementary sub-route (called an LA arc) for each tuple consisting of the following: (1) a customer to begin the LA arc, (2) a customer to end the LA arc, which is far from the first customer, (3) a small set of intermediate customers nearby the first customer. LA routes are constructed by concatenating LA arcs where the final customer in a given LA arc is the first customer in the subsequent LA arc. A Decremental State Space Relaxation (DSSR) method is used to construct the lowest reduced cost elementary route during the pricing step of CG. We demonstrate that LA route based solvers can be used to efficiently tighten the standard set cover vehicle routing relaxation using a variant of subset row inequalities (SRI). However, SRI are difficult to use in practice as they alter the structure of the pricing problem in a manner that makes pricing difficult. SRI in their simplest form state that the number of routes servicing two or three members of a given set of three customers cannot exceed one. We introduce LA-SRI, which in their simplest form state that the number of LA arcs (in routes in the solution) including two or more members of a set of three customers (excluding the final customer of the arc) cannot exceed one. We exploit the structure of LA arcs inside a Graph Generation based formulation to accelerate convergence of CG. We apply our LA-SRI to CVRP and demonstrate that we tighten the LP relaxation, often making it equal to the optimal integer solution, and solve the LP efficiently without altering the structure of the pricing problem.

 

Authors: Amelia Regan, Udayan Mandal, Julian Yarkony
Recommended Citation:
Mandal, U., Regan, A., & Yarkony, J. (2022). Local Area Subset Row Inequalities for Efficient Exact Vehicle Routing. arXiv preprint arXiv:2209.12963.
Article

Giving Curb Visibility to Delivery Drivers

 
Download PDF  (2.14 MB)
Publication: American Planning Association | 2022 State of Transportation Planning
Pages: 134-143
Publication Date: 2022
Summary:
At the time we are writing this article, hundreds of thousands of delivery vehicles are getting ready to hit the road and travel across U.S. cities to meet the highest peak of demand for ecommerce deliveries during Thanksgiving, Black Friday, and the Christmas holiday season. This mammoth fleet will not only add vehicle miles traveled through urban centers but also increase parking congestion, battling with other vehicles for available curb space.
While the integration of road traffic data with modern navigation systems has seen huge developments in the past decade, drastically changing the way we, and delivery vehicles, navigate through cities, not as much can be said when it comes to parking. The task of finding and securing parking is still left to drivers, and largely unsupported by real-time information or app-based solutions.
Delivery vehicle drivers are affected by curb parking congestion even more than any other driver because delivery drivers have to re-park their vehicles not once or twice, but 10, 20, or even more times during a delivery route.
Our work, discussed in this article, focuses on improving delivery drivers’ lives when it comes to finding available curb space, improving the delivery system, and reducing some of the externalities generated in the process. We first describe what types of parking behaviors delivery drivers adopt when facing a lack of available curb parking, then we will quantify the cost of lack of available parking, estimating how much time delivery drivers spend circling the block and searching for parking. We then discuss how we can improve on that by creating the first curb availability information system – OpenPark.

 

Recommended Citation:
Dalla Chiara, Giacomo and Anne Goodchild. Giving Curb Visibility to Delivery Drivers. Intersections + Identities: State of Transportation Planning 2022, 134-143.
Article

Physics-Informed Machine Learning of Parameterized Fundamental Diagrams

 
Download PDF  (2.10 MB)
Publication: arXiv
Volume: 2208.0088
Publication Date: 2022
Summary:

Fundamental diagrams describe the relationship between speed, flow, and density for some roadway (or set of roadway) configuration(s). These diagrams typically do not reflect, however, information on how speed-flow relationships change as a function of exogenous variables such as curb configuration, weather or other exogenous, contextual information. In this paper we present a machine learning methodology that respects known engineering constraints and physical laws of roadway flux–those that are captured in fundamental diagrams– and show how this can be used to introduce contextual information into the generation of these diagrams. The modeling task is formulated as a probe vehicle trajectory reconstruction problem with Neural Ordinary Differential Equations (Neural ODEs). With the presented methodology, we extend the fundamental diagram to non-idealized roadway segments with potentially obstructed traffic data. For simulated data, we generalize this relationship by introducing contextual information at the learning stage, i.e. vehicle composition, driver behavior, curb zoning configuration, etc, and show how the speed-flow relationship changes as a function of these exogenous factors independent of roadway design.

Authors: Thomas MaxnerDr. Andisheh Ranjbari, James Koch, Vinay Amatya, Chase Dowling
Recommended Citation:
Koch, J., Maxner, T., Amatya, V.C., Ranjbari, A., & Dowling, C.P. (2022). Physics-informed Machine Learning of Parameterized Fundamental Diagrams.
Article

Urban Freight Innovation: Leading-Edge Strategies for Smart Cities

 
Download PDF  (1.12 MB)
Publication: Coast Guard Journal of Safety & Security at Sea, Proceedings of the Marine Safety & Security Council
Volume: 78:02:00
Publication Date: 2021
Summary:

Competition throughout the urban freight supply chain is steadily growing. Companies need to devise innovative methods for the transportation of goods from raw materials all the way to the final consumer. From concept to practice, it can be challenging to identify affordable solutions. This article highlights recent research conducted by the University of Washington’s Urban Freight Lab and its partners to explore new methods to reduce transportation costs, improve the customer experience, reduce carbon footprint, and reduce urban congestion after goods leave the shipping docks.

Recommended Citation:
Bill Keough, Anne Goodchild, & Giacomo Dalla Chiara. (2021). Urban Freight Innovation: Leading-Edge Strategies for Smart Cities. Proceedings of the Marine Safety & Security Council, 78(2).
Article

Demand-Driven Supply Chain Meets Offshoring: Looking to go offshore, or improve your current offshore operations? A demand-driven supply chain strategy may be the answer. Here’s how to build one.

 
Download PDF  (1.01 MB)
Publication: Supply Chain Management Review
Volume: 11
Publication Date: 2007
Summary:

Looking to go offshore, or improve your current offshore operations? A demand-driven supply chain strategy may be the answer. Here’s how to build one.

“I’d like the filet mignon—please make that well done, but juicy!” As anyone who’s ever waited tables knows, sometimes the requests you get are just unrealistic. But is this particular customer’s order any less realistic than the CEO announcing: “I’d like to move all production to China, but without increasing inventory or affecting service levels!”

Fortunately, we as operations managers have more tools at our disposal to respond to the CEO’s request that the waiter has to that diner. This column addresses those options. We assume that you have weighed the impact on your total cost to serve and ability to meet your customer demands, and have determined that off-shore sourcing and/or manufacturing is your best option. Our goal here is to help you improve that performance, especially as the speed of market change continually increases, and customer demands intensify. Simply put, we believe that the key to success in the global arena lies in two critical activities: (1) improving the demand signal and (2) decreasing the response time.

Authors: Bill Keough, Mike Ledyard
Recommended Citation:
Keough, Bill. Lee, H. (2007). Demand-driven supply chain meets offshoring. Supply Chain Management Review, 11.