The 14th of October, 2019, Yuan Yuan succesfully defended his thesis titled
Models and algorithms for the last mile delivery with multiple shipping options.
The jury was composed by:
- Claudia Archetti, Professor, ESSEC Paris
- Diego Cattaruzza, Associate Professor, Centrale Lille
- Yves Crama, Professor, Université de Liège
- Dominique Feillet, Professor, Ecole des Mines de Saint-Etienne
- Martine Labbé, Professor, Université Libre de Bruxelles
- Maxime Ogier, Associate Professor, Centrale Lille
- Guido Perboli, Associate Professor, Università di Torino
- Caroline Prodhon, Associate Professor, Université de Technologie de Troyes
- Frédéric Semet, Professor, Centrale Lille
Thesis abstract: E-commerce is a thriving market around the world and suits very well the busy lifestyle of today’s customers. An annual survey by analytics firm comScore and UPS revealed that consumers in US purchased more things online than in stores in 2016. eMarketer estimated that e-commerce sales would top $4 trillion in 2020. This growing e-commerce poses a huge challenge for transportation companies, especially in the last mile delivery.
Nowadays, the most common delivery service is home/workplace delivery. Customers wait at home/workplace to get their orders. Besides, companies like Amazon and FedEx, develop locker delivery. When customers shop online, they can choose a nearby locker as a pickup location. In the past two years, a new concept called trunk delivery, has been proposed. Here, customers’ orders can be delivered to the trunk of their car. Volvo launched its in-car delivery service in Sweden in 2016. The courier has a one-time digital code to get access to the car. Trunk delivery is different from home delivery and locker delivery since the car moves during the day and can be in different locations during different periods of time.
Our intention is to develop an efficient last mile delivery solving method that combines all these delivery services: home/workplace, locker/pickup points and car trunk. In this thesis, we initially present a classification of non-hamiltonian routing problems. These problems are characterized by the fact that not all the locations present in the network need to be visited by the couriers.
Then we study problems that arise from the last mile delivery system that consider multiple delivery services, including home delivery, locker delivery and car trunk delivery. Customers can choose to receive online orders at home, or choose a nearby locker as a pickup location for their orders, or choose to receive their orders in the trunks of their cars. We study the one vehicle case version of the problem, which is called the generalized traveling salesman problem with time windows (GTSPTW). We propose four mixed integer programming formulations for the GTSPTW. The theoretical relations between the relaxations of these formulations are established. Then we design a branch-and-cut algorithm to solve the GTSPTW. We present several problem-specific valid inequalities, which are separated dynamically inside the branch-and-cut algorithm. An initial upper bound is provided by a simple and fast heuristic. We propose different sets of instances characterized by their time window structures. Experimental results show that our algorithm is effective and based on the best formulation, instances with up to 30 clusters can be solved to optimality within one hour.
Finally, we study the multi-vehicle case. The problem that arises is called the generalized vehicle routing problem with time windows (GVRPTW). We propose a dedicated column generation based heuristic: an initial set of routes is determined by heuristic construction of several solutions. The set of routes is then enriched by route optimization methods that seek to generate negative reduced cost routes. Experimental results show that our algorithm is very efficient and can solve the big instances in the literature 100 times quicker, meanwhile improve the solution quality in most cases.
