A savings based method for real-life vehicle routing problems
提出一种基于节约法的算法求解扩展车辆路径问题，与顺序插入法在真实数据上比较，发现节约法在传统指标（总距离、工作量）和非传统指标（路线视觉吸引力）上均表现更好。
This paper describes a Savings Based algorithm for the Extended Vehicle Routing Problem. This algorithm is compared with a Sequential Insertion algorithm on reallife data. Besides the traditional quality measures such as total distance traveled and total workload, we compare the routing plans of both algorithms according to nonstandard quality measures that help to evaluate the "visual attractiveness" of the plan. Computational results show that, in general, the Savings Based algorithm not only performs better with respect to these non-standard quality measures, but also with respect to the traditional measures. Keywords: distribution; road transport; vehicle routing 1 1. Introduction Ever since Dantzig and Ramser [4] first studied the vehicle routing problem (VRP) in 1959, researchers have spent a lot of time and effort on developing methods to tackle this problem. This is due to the fact that the VRP plays a central role in distribution management. In its most simple form, the pr...