Lower Bound Analysis of the Capacitated Vehicle Routing Problem with Unsplit Demands  

作　　者：LIU Min ZHU Chongjun WU Cheng 

机构地区：[1]Department of Automation, Tsinghua University, Beijing 100084, China

出　　处：《Chinese Journal of Electronics》2006年第1期85-90,共6页电子学报（英文版）

基　　金：This work is supported by National Key Basic Research and Development Program （No.2002CB312200） and by the National Natural Science Foundation of China （No.60004010, No.60274045, No.60443009）.

摘　　要：The Capacitated vehicle routing problem （CVRP） with unsplit demands is a kind of special VRP which exists in many technical fields, such as vehicle scheduling in logistics optimization and intelligent transportation, network routing, flow scheduling and so on. In this paper, aiming at the CVRP, we study its lower bound which can be used as the algorithm evaluation criterion. Firstly, we partition the Euclidean plane into a sequence of concentric cirques so that the customer set can be divided into several concentric sets according to the Euclidean distances between the customers and the depot. Furthermore, by the inequality transformation which can be restricted in a relatively small range, we obtain directly the lower bound with parameter for the CVRP without distribution information of the customer demands and locations. Additionally, when the distributions of the customer demands and locations are all independent and identically distributed （i.i.d.）, the lower bound without parameter on the optimal solution value can be obtained. And, the above two lower bounds obtained can be used to evaluate the algorithm performance of the CVRP conveniently. Furthermore, we analyze the relative deviation of the lower bound without parameter under the worst situation. At last, we analyze the lower bound for a kind of special CVRP.

关 键 词：Capacitated vehicle routing problem withunsplit demands Vehicle routing problem （VRP） Lower bound OPTIMIZATION 

分 类 号：TN91[电子电信—通信与信息系统]