An adaptive large neighborhood search for heterogeneous vehicle routing problem with time windows

• Main Authors: NGUYEN, Minh Pham Kien, GUNAWAN, Aldy, YU, Vincent F., MISIR, Mustafa
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Adaptive large neighborhood searches; Heterogeneous vehicles; Mass rapid transit; Metaheuristic; Mixed integer linear programming model; Pickup and delivery; Probabilistics; Search-based; Terminal points; Vehicle routing problem with time windows; Databases and Information Systems; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/8316; https://ink.library.smu.edu.sg/context/sis_research/article/9319/viewcontent/An_Adaptive_Large_Neighborhood_Search_for_Heterogeneous_Vehicle_Routing_Problem_with_Time_Windows.pdf
• Institution: Singapore Management University

The heterogeneous vehicle routing problem with time windows (HVRPTW) employs various vehicles with different capacities to serve upcoming pickup and delivery orders. We introduce a HVRPTW variant for reflecting the practical needs of crowd-shipping by considering the mass-rapid-transit stations, as the additional terminal points. A mixed integer linear programming model is formulated. An Adaptive Large Neighborhood Search based meta-heuristic is also developed by utilizing a basic probabilistic selection strategy, i.e. roulette wheel, and Simulated Annealing. The proposed approach is empirically evaluated on a new set of benchmark instances. The computational results revealed that ALNS shows its clear advantage on the instances with the increasing number of vehicles, especially compared to commercial software, CPLEX.