An adaptive memory algorithm for the split delivery vehicle routing problem

作者：Aleman Rafael E; Zhang Xinhui; Hill Raymond R^*

来源：Journal of Heuristics, 2010, 16(3): 441-473.

DOI：10.1007/s10732-008-9101-3

• Adaptive memory
• Vehicle routing
• Split delivery
• Route angle control
• Heuristic
• Variable neighborhood descent

The split delivery vehicle routing problem (SDVRP) relaxes routing restrictions forcing unique deliveries to customers and allows multiple vehicles to satisfy customer demand. Split deliveries are used to reduce total fleet cost to meet those customer demands. We provide a detailed survey of the SDVRP literature and define a new constructive algorithm for the SDVRP based on a novel concept called the route angle control measure. We extend this constructive approach to an iterative approach using adaptive memory concepts, and then add a variable neighborhood descent process. These three new approaches are compared to exact and heuristic approaches by solving the available SDVRP benchmark problem sets. Our approaches are found to compare favorably with existing approaches and we find 16 new best solutions for a recent 21 problem benchmark set.

• 出版日期2010-6