2016/10/05 by Vladimir G. Deı̌neko, Deineko, Vladimir
Computer Science · Engineering · #90-08 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1610.01876
openalex publication_date 2016/10/05 · openalex created_date 2016/10/14 · openalex updated_date 2026/07/28
In this paper we consider a 2-vehicle routing problem which can be viewed as a building block for the varieties of the vehicle routing problems (VRPs). To approach this problem, we suggest a framework based on the Held and Karp dynamic programming algorithm for the classical travelling salesman problem. An algorithm based on this framework shows an exceptionally good performance on published test data. Our approach can be easily extended to a variety of constraints/attributes in the VRP, hence the wording "small but rich" in the title of our paper.