带收益的车辆路径问题研究综述

《带收益的车辆路径问题研究综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2010年lO月沈阳航窄工业学院学报第27卷第5期JournalofShenyangInstituteofAeronauticalEngineeringOct．20lOV01．27No．5文章编号：1007—1385(，2010)05—0082—05带收益的车辆路径问题研究综述李琳1刘涛2(1．沈阳航空航天大学理学院，辽宁沈阳110136；2．东北大学材料与冶金学院，辽宁沈阳110819)摘要：车辆路径问题是企业实现物流配送的关键环节，对带收益的车辆路径问题的研究进行了综述。根据目前该问题的研究进展，对相关的研究进行了分类；分析了该类问题的特点，探讨了相

2、应的0—1整数规划模型及集划分模型，总结了求解该问题的精确算法与启发式算法。介绍了该问题在实际中的应用，展望了其研究前景，为相关研究指出了方向。关键词：带收益的车辆路径问题；数学模型；精确算法；启发式算法中图分类号：TP301．6文献标识码：Adoi：10．3969／j．issn．1007—1385．2010．05．018车辆路径问题是物流配送过程中的关键环节，选取适当的车辆路径可以加快对顾客需求的响应速度，提高企业的服务质量，增加客户对物流环节的满意度，对降低企业的运作成本、提高企业形象及其竞争力具有十分重要的意义。车辆路径问题是由Dantzig¨1首

3、次提出的，其一般定义为对一系列发货点和收货点组织适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下(如货物需求量、发送量、交发货时间、车辆的容量限制、行驶里程限制、行驶时间限制等)实现一定的目标(行驶路程最短、总运费最少、总行驶时间最少、总使用车辆数最少等)。该问题的特点是每个顾客点都被访问到一次且只能由一辆车访问。实际问题中存在这样一类问题：车辆数目一定，由于车辆最长服务时间或最大容量等方面的限制，车辆在相关约束条件下只能访问部分顾客点，而每辆车在访问某一顾客点时会得到相应的收益，每个顾客点只能由一辆车访问。因此，需要讨论在满足车辆相应约束的

4、条件下收益最大的车辆路径问题，即带收益的车辆路径问题¨1(VehicleRoutingProblemwithProfits，VR—PP)。该问题也常称作可选择的车辆路径问题∞1(SelectiveVehicleRoutingProblem，SVRP)或多环游路径最大收集问题H。1(multipletourmaximumcollectionproblem)o收稿日期：2010一Ol一12基金项目：国家自然科学基金资助项目(项目编号：50904016)作者简介：李琳(1978一)，女，吉林吉林人，讲师，主要研究方向：系统建模、算法优化，E—mail：LL49

5、705055@126．corn。1带收益的车辆路径问题分类及数学模型1．1VRPP的分类根据问题的目标函数及其约束情况，可将该问题分为以下3类：(1)多目标带收益的车辆路径问题。目标函数为最小化总的车辆行驶费用、最大化总的利润收益等。多目标问题也可以通过加权使其转化为单目标问题。当仅有一辆车时，该类问题又称为带收益的环游问题16o(profitabletourproblem)；(2)若将车辆行驶费用作为约束条件，在行驶费用不超过现有费用C～的条件下，使总收益最大。当车辆数为1时，该问题又称为定向越野竞赛问题"。8o(orienteeringproblem

6、)；(3)若将收益作为约束条件，在收益不小于价值R耐。的条件下，使总的行驶费用最小。当车辆数为1时，该问题又成为奖金收集旅行商问题旧叫¨(prize—collectingTSP)。1．2V跗'P的数学模型1．2．10一l整数规划模型设一完全图G(N，A)，N={0，1，2，⋯，n}为节点集合，其中节点0为车场，共有／／,个顾客点。弧集合A={(i，-『)Ii√EN}。第一类问题的模型如下：MaxZ=乏(善Piy：一卢∑∑do．石：)(1)^IE“、10t‘EⅣJEN‘，．，第4期李琳等：带收益的车辆路径问题研究综述∑《=∑《i∈Ⅳ而∈K

7、e^Je^i}l

8、i≠l∑x：=y：i∈，v＼IolJ

9、}∈KJEⅣI产J(2)(3)仉∑石岳≥∑qiY：

10、

11、}∈K(4)iEV、10}iE，v、}0fui一吩+QI髫：+(QI—gi一田)x；sQ女一q，i√∈Ⅳ＼{0}i≠，J

12、}∈Ki5)gi≤Ⅱ。5QIi∈Ⅳ＼{0}后∈K(6)，，：，戈：∈{0，1}i√∈N后EK(7)其中，Pi是顾客点i被访问时得到的收益，P。=0。qi是顾客点i的需求，q。=00di是点i与，之问的距离。p是单位距离的行驶费用，Q是车辆的容量，K为车辆集合，“。是与点i有关的重量，其值介于顾客需求与车辆能力之间。目标函数(1)是最大化总收益，

13、总收益等于访问各顾客点获得的收益总和减去行驶费用。约束(2)是集合Ⅳ中各顶点的度