1437. Combining vehicle routing with transportation on a ring in city logistics: a branch-and-price approach
Invited abstract in session WA-17: Combinatorial optimization in distribution and delivery operations, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Laurent Alfandari
|
| ESSEC Business School | |
| 2. | Paolo Gianessi
|
| Mines Saint-Etienne, Univ. Clermont Auvergne, CNRS, UMR 6158 LIMOS, Institut Henri Fayol, F - 42023 Saint-Etienne France |
Abstract
In the Multi-commodity Ring Vehicle Routing Problem (MRVRP), goods are collected from virtual gates outside the city, then transit through one or several depots called Urban Distribution Centers before being delivered to customers in either open or closed delivery routes. The reverse pick-up trip from customers to gates via UDCs is also considered. The UDCs are located around the city and connected by a ring using transportation modes with low per-unit emission costs, such as high-capacity trucks or railway shuttles. Such a ring system circulation, together with a fleet of electric vans to perform the routing inside the city, matches increasing urban traffic restrictions that prevent large trucks from getting into the city center. The City Logistics problem that is the closest to the MRVRP is the Two-Echelon Vehicle Routing Problem, but has different features and no ring structure. We consider repositionning constraints at UDCs and design an efficient Branch-and-Price algorithm to solve the problem. The decompositon assigns the routing part to the pricing subproblem. This pricing problem is an elementary shortest path problem with resource constraints solved with Dynamic Programming, accelerated with q-routes and ng-paths. The numerical results show the performance of the method and an extensive sensitivity analysis is carried out on key problem parameters.
Keywords
- Vehicle Routing
- Column Generation
- Combinatorial Optimization
Status: accepted
Back to the list of papers