Hybrid Heuristics for The Dial-A-Ride Problem with Transfer and Synchronization in Central Hub
Abstract
This paper deals with the dial-a-ride problem with transfer, where a set of customer demands are divided into two different regions, such as the pickup and delivery nodes must not be in the same region for a given request. Two vehicles are needed to meet customer demand which implies a synchronization process between vehicles in the transfer point called a central hub. In this paper, we provide a solution method based on an adaptive large neighborhood search algorithm (ALNS), to stretch the neighborhood of a solution, which gives the best search space exploration. Effificient constructions methods are proposed to repair a destroyed solution, giving a large possibility case. An intensifification mechanism is ensured by blending the proposed ALNS with TS and SA algorithms. Implemented algorithms outperform all comparison methods such as memetic algorithms regardless of the quality solution and the run-time for all existing benchmarks sets.References
G.B.Bdantzig, B.George and H.J.Ramser, The truck dispatching problem, Management science, 1959, vol. 6, no 1, p. 80–91.
G.Clarke and J.W.Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 1964, vol. 12, no 4, p. 568–581.
S.Hammouda, M.Taffar and A.Lemouari, A Simulated Annealing for The Resolution of ”Dial-A-Ride-Problem with Transfer” Using Hybrid Neighborhood Methods, IEEE 2nd International Conference on Electronics, Control, Optimization and Computer Science (ICECOCS). IEEE, 2020. p. 1-6.
B.L.Golden, S.Raghavan and E.A.Wasil, The vehicle routing problem: latest advances and new challenges, Springer Science and Business Media, 2008.
S.N.Parragh, K.F.Doerner and R.Hartl, A survey on pickup and delivery problems, Journal f¨ur Betriebswirtschaft, 2008, vol. 58, no 2, p. 81–117.
R.Chevrier, A.Liefooghe, L.Jourdan and C.Dhaenens, Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport, Applied Soft Computing, 2012, vol. 12, no 4, p. 1247–1258.
J.F.Cordeau and G.Laporte, The dial-a-ride problem: models and algorithms, Annals of operations research, 2007, vol. 153, no 1, p. 29–46.
R.Masson, F.Lehu´ed´e and O.P´eton, The dial-a-ride problem with transfers, Computers and Operations Research, 2014, vol. 41, p. 12–23.
D.M.Stein, Scheduling dial-a-ride transportation systems, Transportation Science, 1978, vol. 12, no 3, p. 232–249.
J.S.Shang and C.K.Cuff, Multicriteria pickup and delivery problem with transfer opportunity, Computers and Industrial Engineering, 1996, vol. 30, no 4, p. 631–645.
S.R.Thangiah, R.SAM, A.Fergany and S.Awan, Real-time split-delivery pickup and delivery time window problems with transfers, Central European Journal of Operations Research, 2007, vol. 15, no 4, p. 329–349.
C.E.Cort´es, M.Matamalat and C.Contardo, The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method, European Journal of Operational Research, 2010, vol. 200, no 3, p. 711–724.
P.Bouros, D.Sacharidis, T.Dalamagas and T.Sellis, Dynamic pickup and delivery with transfers, International Symposium on Spatial and Temporal Databases. Springer, Berlin, Heidelberg, 2011. p. 112–129.
Y.Qu and J.F.Bard, A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment, Computers and Operations Research, 2012, vol. 39, no 10, p. 2439–2456.
R.Masson, F.Lehu´ed´e and O.P´eton, An adaptive large neighborhood search for the pickup and delivery problem with transfers, Transportation Science, 2013, vol. 47, no 3, p. 344–355.
S.Deleplanque and A.Quilliot, Dial-a-ride problem with time windows, transshipments, and dynamic transfer points, IFAC Proceedings Volumes, 2013, vol. 46, no 9, p. 1256–1261.
J.F.Cordeau and G.Laporte, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transportation Research Part B: Methodological, 2003, vol. 37, no 6, p. 579–594.
K.Braekers, A.Caris and G.K.Janssens, Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots, Transportation Research Part B: Methodological, 2014, vol. 67, p. 166–186.
S.N.Parragh, J.Pinho de Sousa and B.Almada-Lobo, The dial-a-ride problem with split requests and profits, Transportation Science, 2015, vol. 49, no 2, p. 311–334.
F.Neves-Moreira, P.Amorim, L.Guimar˜aes and B.Almada-Lobo, A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations, European Journal of Operational Research, 2016, vol. 248, no 2, p. 487–506.
J.Sch¨onberger, Scheduling constraints in dial-a-ride problems with transfers: a metaheuristic approach incorporating a cross-route scheduling procedure with postponement opportunities, Public Transport, 2017, vol. 9, no 1, p. 243–272.
N.Danloup, H.Allaoui and G.Goncalves, A comparison of two meta-heuristics for the pickup and delivery problem with transshipment, Computers and Operations Research, 2018, vol. 100, p. 155–171.
D.Wolfiner and J.J.Salazar-Gonz´alez, The pickup and delivery problem with split loads and transshipments: A branch-and-cut solution approach, European Journal of Operational Research, 2021, vol. 289, no 2, p. 470–484.
H.L.M.Kerivin, M.Lacroix, A.R.Mahjoub and A.Quilliot, The splittable pickup and delivery problem with reloads, European Journal of Industrial Engineering, 2008, vol. 2, no 2, p. 112–133.
S.Ropke and J.F.Cordeau, Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 2009, vol. 43, no 3, p. 267–286.
D.Pisinger and S.Ropke, A general heuristic for vehicle routing problems, Computers and operations research, 2007, vol. 34, no 8, p. 2403–2435.
S.Ropke and D.Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science, 2006, vol. 40, no 4, p. 455–472.
P.Shaw, Using constraint programming and local search methods to solve vehicle routing problems, International conference on principles and practice of constraint programming. Springer, Berlin, Heidelberg, 1998. p. 417–431.
M.A.Masmoudi, M.Hosny, K.Braekers and A.Dammak, Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem, Transportation Research Part E: Logistics and Transportation Review, 2016, vol. 96, p. 60–80.
Y.Li, H.Chen and C.Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European Journal of Operational Research, 2016, vol. 252, no 1, p. 27–38.
B.Li, D.Krushinsky, T.Van Woensel and H.A.Reijers, An adaptive large neighborhood search heuristic for the share-a-ride problem, Computers and Operations Research, 2016, vol. 66, p. 170–180.
P.Shaw, A new local search algorithm providing high quality solutions to vehicle routing problems, APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 1997.
F.Glover and M.Laguna, Tabu search, Handbook of combinatorial optimization. Springer, Boston, MA, 1998. p. 2093–2229.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
