An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization.

*(English)*Zbl 1346.90116Summary: The two-echelon vehicle routing problem (2E-VRP) consists in making deliveries to a set of customers using two distinct fleets of vehicles. First-level vehicles pick up requests at a distribution center and bring them to intermediate sites. At these locations, the requests are transferred to second-level vehicles, which deliver them. This paper addresses a variant of the 2E-VRP that integrates constraints arising in city logistics such as time window constraints, synchronization constraints, and multiple trips at the second level. The corresponding problem is called the two-echelon multiple-trip vehicle routing problem with satellite synchronization (2E-MTVRP-SS). We propose an adaptive large neighborhood search to solve this problem. Custom destruction and repair heuristics and an efficient feasibility check for moves have been designed and evaluated on modified benchmarks for the VRP with time windows.

##### Keywords:

routing; two-echelon VRP; synchronization; city logistics; adaptive large neighborhood search
PDF
BibTeX
XML
Cite

\textit{P. Grangier} et al., Eur. J. Oper. Res. 254, No. 1, 80--91 (2016; Zbl 1346.90116)

Full Text:
DOI

##### References:

[1] | Azi, N.; Gendreau, M.; Potvin, J.-Y., An adaptive large neighborhood search for a vehicle routing problem with multiple routes, Computers & Operations Research, 41, 167-173, (2014) · Zbl 1348.90065 |

[2] | Bortfeldt, A.; Hahn, T.; Männel, D.; Mönch, L., Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints, European Journal of Operational Research, 243, 82-96, (2015) · Zbl 1346.90079 |

[3] | Breunig, U., Schmid, V., Hartl, R. F., & Vidal, T. (2015). A fast large neighbourhood based heuristic for the two-echelon vehicle routing problem. Working Paper. · Zbl 1349.90073 |

[4] | Cattaruzza, D.; Absi, N.; Feillet, D.; González-Feliu, J., Vehicle routing problems for city logistics, EURO Journal on Transportation and Logistics, 1-29, (2015) |

[5] | Cattaruzza, D.; Absi, N.; Feillet, D.; Vigo, D., An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows, Computers & Operations Research, 51, 257-267, (2014) · Zbl 1348.90074 |

[6] | Cormen, T. H.; Leiserson, C. E.; Ronald, R. L.; Stein, C., Introduction to algorithms, (2010), The MIT Press |

[7] | Crainic, T. G.; Mancini, S.; Perboli, G.; Tadei, R., Clustering-based heuristics for the two-echelon vehicle routing problem, Technical Report, CIRRELT-2008-46, (2008), CIRRELT |

[8] | Crainic, T. G.; Mancini, S.; Perboli, G.; Tadei, R., Multi-start heuristics for the two-echelon vehicle routing problem, (Merz, P.; Hao, J.-K., Evolutionary computation in combinatorial optimization, (2011), Springer), 179-190 |

[9] | Crainic, T. G.; Mancini, S.; Perboli, G.; Tadei, R., GRASP with path relinking for the two-echelon vehicle routing problem, Advances in Metaheuristics, 53, 113-125, (2013) |

[10] | Crainic, T. G.; Perboli, G.; Mancini, S.; Tadei, R., Two-echelon vehicle routing problem: a satellite location analysis, Procedia - Social and Behavioral Sciences, 2, 3, 5944-5955, (2010) |

[11] | Crainic, T. G.; Ricciardi, N.; Storchi, G., Advanced freight transportation systems for congested urban areas, Transportation Research Part C: Emerging Technologies, 12, 2, 119-137, (2004) |

[12] | Crainic, T. G.; Ricciardi, N.; Storchi, G., Models for evaluating and planning city logistics systems, Transportation Science, 43, 4, 432-454, (2009) |

[13] | Cuda, R.; Guastaroba, G.; Speranza, M., A survey on two-echelon routing problems, Computers & Operations Research, 1-15, (2014) · Zbl 1348.90078 |

[14] | Drexl, M., Synchronization in vehicle routing-A survey of VRPs with multiple synchronization constraints, Transportation Science, 46, 3, 297-316, (2012) |

[15] | Hemmelmayr, V. C.; Cordeau, J.-F.; Crainic, T. G., An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Computers & Operations Research, 39, 12, 3215-3228, (2012) · Zbl 1349.90858 |

[16] | Jepsen, M.; Spoorendonk, S.; Ropke, S., A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem, Transportation Science, 47, 1, 23-37, (2013) |

[17] | Kovacs, A.; Parragh, S.; Doerner, K.; Hartl, R., Adaptive large neighborhood search for service Technician routing and scheduling problems, Journal of Scheduling, 15, 5, 579-600, (2012) |

[18] | Mancini, S., Multi-echelon distribution systems in city logistics, European Transport/Trasporti Europei, 54, (2013) |

[19] | Masson, R.; Lehuédé, F.; Péton, O., An adaptive large neighborhood search for the pickup and delivery problem with transfers, Transportation Science, 47, 3, 344-355, (2013) |

[20] | Masson, R.; Lehuédé, F.; Péton, O., Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers, Operations Research Letters, 41, 3, 211-215, (2013) · Zbl 1286.90085 |

[21] | Masson, R.; Lehuédé, F.; Péton, O., The dial-a-ride problem with transfers, Computers & Operations Research, 41, 12-23, (2014) · Zbl 1348.90111 |

[22] | Masson, R.; Trentini, A.; Lehuédé, F.; Malhéné, N.; Péton, O.; Tlahig, H., Optimization of a city logistics transportation system with mixed passengers and goods, EURO Journal on Transportation and Logistics, 1-29, (2015) |

[23] | Nguyen, P. K.; Crainic, T. G.; Toulouse, M., A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows, European Journal of Operational Research, 231, 1, 43-56, (2013) · Zbl 1317.90332 |

[24] | Nguyen, V.-P.; Prins, C.; Prodhon, C., Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking, European Journal of Operational Research, 216, 1, 113-126, (2012) · Zbl 1237.90047 |

[25] | Perboli, G.; Tadei, R., New families of valid inequalities for the two-echelon vehicle routing problem, Electronic Notes in Discrete Mathematics, 36, 639-646, (2010) · Zbl 1237.90023 |

[26] | Perboli, G.; Tadei, R.; Vigo, D., The two-echelon capacitated vehicle routing problem: models and math-based heuristics, Transportation Science, 45, 3, 364-380, (2011) |

[27] | Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Computers & Operations Research, 34, 8, 2403-2435, (2007) · Zbl 1144.90318 |

[28] | Qu, Y.; Bard, J. F., A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment, Computers & Operations Research, 39, 10, 2439-2456, (2012) · Zbl 1251.90059 |

[29] | Roberti, R., Exact algorithms for different classes of vehicle routing problems, (2012), Bologna., (Ph.D. thesis) |

[30] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472, (2006) |

[31] | Santos, F. A.; Cunha, A. S.; Mateus, G. R., Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem, Optimization Letters, 7, 7, 1537-1547, (2012) · Zbl 1274.90238 |

[32] | Santos, F. A.; Mateus, G. R.; da Cunha, A. S., A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem, Transportation Science, Articles i, April, 1-14, (2014) |

[33] | Savelsbergh, M. W.P., Local search in routing problems with time windows, Annals of Operations Research, 4, 1, 285-305, (1985) |

[34] | Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, Fourth international conference on principles and practice of constraint programming, 417-431, (1998) |

[35] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problem with time window constraints, Operations Research, 35, 2, 254-265, (1987) · Zbl 0625.90047 |

[36] | Taillard, E. D.; Laporte, G.; Gendreau, M., Vehicle routing with multiple use of vehicles, Journal of the Operational Research Society, 47, 1065-1070, (1996) · Zbl 0864.90045 |

[37] | Zeng, Z.-Y.; Xu, W.; Xu, Z.-Y.; Shao, W.-H., A hybrid GRASP+ VND heuristic for the two-echelon vehicle routing problem arising in city logistics, Technical Report, (2014), School of Electronics and Information Engineering, Tongji University |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.