Optimization of Urban Synchromodal Systems – OPUSS

The main ambition of the project is to hybridize the traditional solution methods used by each of the two research teams involved in the project.

The team of the University of Mainz has an expertise in the exact solution of combinatorial optimization problems, in particular with column generation techniques. The LS2N team has expertise in the heuristic solutions methods, in particular with the Large Neighborhood Search (LNS) metaheuristic.

The research program includes phases during which the two teams solve city logistics optimization problems in a disjoint manner, each with its own methods. The project also includes phases in which the two teams pool their expertise, in order to develop so-called matheuristic methods, i.e. combining exact and heuristic solution methods.

An example is the strengthening of the LNS algorithm used to solve the problem of vehicle rounds with delivery options, using set partitioning techniques and the neighborhood proposed by Balas and Simonetti. Another example is the use of LNS to generate a set of routes that will be used as «raw material« by a column generation algorithm.

After two and a half years of work, the work on the vehicle routing problem with delivery options has resulted in two publications in international journals. A third article measuring the interest of reinforcing the LNS method by set partitioning and Balas-Simonetti neighborhood approaches is under review.

Important research efforts have been devoted to the solution of the two-echelon vehicle routing problem (VRP-2E), with simultaneous presence of direct and reverse flows. To solve this extremely difficult problem, exact and heuristic solution methods have been combined and a matheuristic algorithm has been developed. A paper will be submitted for publication soon.

More generally, the project has allowed the two research teams to compare their approaches to solving the problem and thus enrich their field of expertise.

The immediate prospects concern the refinement of the algorithm developed for the VRP-2E with inbound and outbound flows. In particular, the possibility of delivering to final customers from the first echelon is a realistic extension of our study.

The current work is oriented towards extensions of the truck and trailer problem. More precisely, the aim is to consider distribution models where the driver park their vehicle at selected placed and can walk the last meters (or hectometers) to deliver their customers. This problem can then be extended to the case where the vehicles carry several drivers.

The algorithms developed can be extended to a wide variety of optimization problems with similar characteristics.

The OPUSS project has been carried out concurrently with several applied research projects in urban logistics, whose future publications will help the team to position itself as a major player in this research field.

INTERNATIONAL JOURNAL PAPERS:

A Large Neighborhood Search approach to the Vehicle Routing Problem with Delivery Options, D Dumez, F Lehuédé, O Péton, Transportation Research Part B: Methodological 144, 103-132, 2021.

The Last-mile Vehicle Routing Problem with Delivery Options, C. Tilk, K. Olkis, S. Irnich, to appear in OR Spectrum, 2021.

Hybridizing Large Neighborhood Search and Exacts Methods for Generalized Vehicles Routing Problems with Time Windows, D Dumez, C Tilk, S Irnich, F Lehuédé, O Péton. Submitted to EJTL, 2021.


A matheuristic for a 2-echelon-vehicle routing problem with satellite capacities and reverse flows, D Dumez, C. Tilk, S. Irnich, F. Lehuédé, K. Olkis, O. Péton, 2021.

INTERNATIONAL CONFERENCES:

Large Neighborhood Search with set partitioning and dynamic programming for the VRP with Delivery Options, D Dumez, I Stefan, F Lehuédé, K Olkis, O Péton, C Tilk, SynchroTrans 2019, Nantes.

Vehicle Routing Problem with Alternative Delivery Options and Customer Preferences, O Péton, D Dumez, F Lehuédé, IWUOR 2019, Nagoya.

Integrating lockers and multiple delivery options in a city logistics distribution system, D Dumez, F Lehuédé, O Péton, EURO 2019, Dublin.

A Large Neighborhood Search approach to integrate delivery options in last mile delivery, D. Dumez, F. Lehuédé, O. Péton, VeRoLog 2019, Sevilla.

The Last-mile Vehicle Routing Problem with Delivery Options, C. Tilk, K. Olkis, S. Irnich, , VeRoLog, 2019, Sevilla.


NATIONAL CONFERENCES:


Renforcements de la recherche à voisinage large pour les problèmes de tournées de véhicules généralisés, D. Dumez, K. Olkis, S. Irnich, F. Lehuédé, O. Péton, C. Tilk, ROADEF 2020, Montpellier, 2020.

The Last-mile Vehicle Routing Problem with Delivery Options, K. Olkis, C. Tilk, S. Irnich, OR 2019, Dresde.

City logistics projects have shown that urban freight networks should rely on the interoperability of several layers and modes of transportation for the delivery to shops and consumers from urban consolidation centers. In long-haul transportation, this is known as synchromodality. The concept refers to a global optimization of the network by synchronizing all transportation modes including flexible dedicated vehicles and scheduled lines. Through synchromodal transportation, the carriers and/or customers select independently at any time the best mode based on the operational circumstances and customer requirements. Synchromodality was introduced to improve the cost, resilience, and energy efficiency of multimodal networks. As a case in point, the last mile delivery is becoming a challenge in large urban areas due to the fast increase of e-commerce. Sustainable and smarter urban management is needed to reduce pollution and congestion and to meet the needs of the population. In line with this observation, new freight transportation modes (electric vehicles, cargo bikes, sharing with public transport) and delivery options (doorstep, lockers, parcel-shops) are being experimented, but rethinking transportation systems as a whole remains a challenge.
The goal of the OPUSS project is to design advanced optimization algorithms to support the planning of synchromodal urban delivery networks. It extends the concept of synchromodality by integrating the most recent urban transportation modes and delivery options proposed as last mile delivery solutions in city logistics. According to this objective, we propose to achieve fundamental advances on two major challenges of synchromodal urban systems: the choice among alternative options to deliver to customers and the temporal synchronization of modes at multiple echelons. The former allows carriers to choose among possible delivery options to produce cost-efficient routes and schedules for their fleet while holding a certain service level. The latter also comprises the handling of forward and reverse flows, mobile bases, and short-term inventories at intermediate urban logistics spaces. Vehicle routes and schedules must be adjusted to cope with all these real-world constraints.
We propose to combine the best principles and components of exact and heuristic optimization algorithms into so-called matheuristic approaches. The consortium thus aims to share a deep expertise in transport synchronization by gathering experts on exact optimization on the one side, and meta-heuristics on the other side. Together, we plan to address algorithmic challenges such as expedient solution representation, efficient feasibility checking, effective heuristics guided by mathematical programming, and heuristic solving of subproblems in exact approaches. The project will be managed in tight cooperation between both groups in Nantes and Mainz with the support of two PhD students.
The expected output of OPUSS is threefold: First, to gain insights into the structure of optimization problems arising in urban synchromodal systems in order to establish the fundamental mathematical properties that support efficient algorithms. Second, OPUSS will deliver the key models and algorithmic components that allow to address the main characteristics of these systems. Third, OPUSS's ultimate goal is to integrate all algorithmic components into a unified algorithm that is easily adaptable to most urban distribution systems. These results are expected to have a high impact for the city logistics and vehicle routing scientific communities as well as for software providers regarding the design of intelligent transportation systems (ITSs) by facilitating the integration of greener transportation modes. In practical terms, the return for carriers is improved efficiency in delivering goods in cities, whereas urban communities will observe reduced freight movements in city centers.