Title: A fast dynamic programming algorithm to a varied capacity problem in vehicle routing

Authors: Pengle Zhang; Yajie Dou

Addresses: College of System Engineering, Academy of Military Sciences, AnXiang North Road No. 10, Beijing, China ' College of Information System and Management, National University of Defense Technology, Changsha, Hunan, China

Abstract: As a typical combinational optimisation problem, the researches on vehicle routing problem (VRP) mostly focus on the case when vehicle loading capability is certain. In fact, the vehicle loading capability often changes with multi-type vehicles, varying goods size and customer's requirement alter. Thus, a varied capacity vehicle routing problem (VCVRP) is introduced and a fast dynamic programming algorithm is presented based on the K-step best fit deceasing and minimum spanning tree methods, the algorithms can serve as an approximate decoupling between the goods packing problem and router selection problem in VCVRP. Besides, the theoretical analysis on the upper bound of vehicle trip and local minimisation based on short-path priority principle are carried out theoretically. Finally, an example about varied capacity vehicle logistics transportation task is given with quality and performance analysis on different parameters and scales, to illustrate the feasibilities and advantages of the proposed algorithm.

Keywords: logistic systems; dynamic programming; varied capacity vehicle routing problem; VCVRP; fast algorithm; heuristic algorithm.

DOI: 10.1504/IJADS.2018.090924

International Journal of Applied Decision Sciences, 2018 Vol.11 No.2, pp.146 - 167

Accepted: 31 Aug 2017
Published online: 03 Apr 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article