Solving Vehicle Routing Problems Using an Enhanced Clarke-Wright Algorithm: A Case Study
A vehicle routing problem (VRP) is an optimization problem encountered in many applications some of them even not directly related to vehicle routing. For a given fleet of vehicles (or service personnel) the goal of a VRP is to seek delivering products or services to various customer doorsteps at minimal cost (that can be represented by travel time, distances, or some customized ones) while satisfying the imposed business rules such as the vehicle capacities, the route length traversed by a vehicle, the working hours (schedules) of a driver or service person. It is known that the VRP is a difficult problem to be solved to its global optimality within a reasonable computational time. In order to solve VRPs from the real world more effectively, many algorithms, particularly heuristics, were designed and implemented to tackle this type of problems. Recently the well-known savings approach of Clarke and Wright was re-considered and some enhanced versions were proposed aiming to achieve improved solutions for the VRP. The goal of this paper is to present a business scenario requiring VRP solutions, and to propose an enhanced Clarke and Wright algorithm in the spirit of those proposed recently to solve the problems of this case study. Furthermore, the proposed algorithm aims at eliminating the human interventions such as parameter setting and tuning during the problem solving procedures. Computational results demonstrate that the new algorithm addresses the business needs better in the real applications and the results obtained by the algorithm are preferred by the end users.
Vehicle Routing Problem Case Study Decision Support Savings Algorithm
Buyang Cao
School of Software Engineering, Tongji University, 4800 Cao An Road, Shanghai, China 201804
国际会议
Third International Conference ,ICCL2012(第三届国际计算物流会议)
上海
英文
190-205
2012-09-24（万方平台首次上网日期，不代表论文的发表时间）