Order-first split-second methods for vehicle routing problems: A review |
| |
| Affiliation: | 1. Southampton Business School, Centre for Operational Research, Management Science and Information Systems (CORMSIS), University of Southampton, Southampton, United Kingdom;2. CIRRELT and HEC Montréal, Montréal, Canada;3. CIRRELT, Canada Research Chair in Distribution Management and HEC Montréal, Montréal, Canada;1. State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, China 430074;2. Walmart Labs, Walmart Inc. Arkansas, USA 72712;3. School of Computer Science, Liaocheng University, Liaocheng, China 252059;4. Jinan University, Guangzhou, China 510632 |
| |
| Abstract: | Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a giant tour covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has nevertheless led to successful metaheuristics for various vehicle routing problems in the last decade. As many implementations consider an ordering of customers instead of building a giant tour, we propose in this paper the more general name of ordering-first split-second methods. This article shows how this approach can be declined for different vehicle routing problems and reviews the associated literature, with more than 70 references. |
| |
| Keywords: | Vehicle routing Metaheuristic Route-first cluster-second heuristic Order-first split-second heuristic Splitting procedure |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
