节点具有双重需求车辆路径问题及其解的性质分析  

Vehicle Routing Problem with Nodes of Double Demands and the Property of Its Solution

作　　者：王科峰[1,2] 叶春明[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]河南理工大学能源科学与工程学院,焦作454000

出　　处：《上海理工大学学报》2013年第4期329-335,共7页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(71271138);教育部人文社会科学规划基金资助项目(10YJA630187);上海市教育委员会科研创新资助项目(12ZS133);高等学校博士点基金资助项目(20093120110008)

摘　　要：概括介绍了逆向物流领域中的各类车辆路径问题,将问题按照节点的需求类型分为节点单需求以及具有双重需求两个大类.按照节点的需求类型,将同时送取货(VRPSDP)、集送货需求可拆分车辆路径问题(SVRPPD)统称为节点具有双重需求车辆路径问题(VRPNDD).文中首先给出了它们的定义及数学模型.接着,作为设计求解问题启发式算法的前期工作,对VRPNDD问题解的结构方面的一些性质进行了分析证明.最后,举例说明了SVRPPD与送货需求可拆分车辆路径问题最优解性质方面的差异,并通过定理证明说明了SVRPPD,VRPSDP启发式算法的改良对于SVRPPD相对VRPSDP节省成本百分比研究的意义.A general outline of various types of vehicle routing problems in the field of reverse logistics was given. The vehicle routing problems were divided into two classes, i. e. the problem of single demand and double demands, according to the demand characteristic of the customer node. The vehicle routing problem with simultaneous delivery and pickup （VRPSDP） and the vehicle routing problem with split deliveries and pickups （SVRPPD） were called as the vehicle routing problem with nodes of double demands （VRPNDD）. Their definitions and mathematic models were given. Then as the preliminary work for designing the heuristics, some constitutive properties of the solution for the VRPNDD were investigated. The difference in properties of optimal solutions between SVRPPD and SDVRP （the vehicle routing problem with split delivery） was illustrated, and a theorem was proved to show the significance of the heuristics＇ improving on cost saving analysis of SVRPPD relative to VRPSDP.

关 键 词：同时送取货 集送货需求可拆分 弱可行解 强可行解 HAMILTON回路 子回路 

分 类 号：O221[理学—运筹学与控制论]