论文部分内容阅读
摘要：基于现代物流业的实际需求，研究了一个带油耗的开放式单车场多车型车辆路径问题。首先建立了该问题的0—1整数规划模型，接着给出一个禁忌搜索算法对该问题进行了求解，在此禁忌搜索算法中，为了提高其性能，采取了如下策略：（1）给出一个改进的最近邻算法来求得问题的一个可行解，并将其作为禁忌搜索算法的初始解；（2）根据车辆有不同的类型而采用了一些特殊的邻域操作。最后举例对该禁忌搜索算法进行说明，并对进一步的研究工作进行了展望。
关键词：开放式车辆路径问题；禁忌搜索算法；0—1整数规划
中图分类号：U116.2 文献标识码：A
车辆路径问题（Vehicle Routing Problem， VRP）最早由Dantzing和Ramser[1]于1959年提出， 之后产生了这一问题的许多变种，例如：多车型车辆路径问题（Heterogeneous—vehicle Vehicle Routing Problem，HVRP）[2—4]；多车场车辆路径问题[5—6]；开放式车辆路径问题[7—11]等等。
针对各种车辆路径问题，大部分文献的目标函数大致由两部分组成：（1）车辆的启动费用；（2）车辆的行驶费用。首先，车行驶费用与行驶距离有关，而现实生活中，随着油价的不断上涨，在考虑车行驶费用的时候除了考虑行驶距离对于行驶费用的影响，耗油量对于行驶费用的影响也是很大的，所以熊浩[12]、唐加福[13]等人在目标函数中考虑了油耗成本对线路的影响，但是他们考虑的都是封闭式车辆路径问题。而由于各厂商现在大部分都采用物流外包，所以有必要考虑路径为开放形式的，这样更符合实际生活，故此本文考虑带油耗的开放式车辆路径问题，即：车辆在对其负责的路径上的客户进行服务时，不必回到原车场，而是终止于它所服务的最后一个客户点。另外，由于一个物流公司所服务的客户其需求不同，因此可能需要该物流公司派出不同类型的车辆对其进行服务，即使所服务的客户没有特殊要求，物流公司本身也可能具有不同型号的车辆，而不同车型的车辆其启动费和最大容量是不同的，由此会对物流公司的车辆分配方案产生影响，所以本文研究的车辆路径问题还要考虑车辆的启动费用及容量。
1 问题描述
2 数学建模
其中：（1）的第一项与第二项分别表示所有配送车辆总的油耗和总的启动费用；（2）表示所用的每类型车车数不超过此类型车数；（3）表示每个客户点恰好被访问一次；（4）表示离开每个客户点的车辆数小于或等于进入该客户点的车辆数；（5）表示被派遣的每一辆车的载重量都不超过其容量。
3 模型求解
因为开放式车辆路径问题（OVRP）是NP难的[8]，而本文讨论的问题是对OVRP的扩展，所以本文的问题也是NP难的，因此下面采用禁忌搜索算法对其进行求解。
3.1 禁忌算法中的初始解的求法
由于禁忌搜索算法求解的好坏在一定程度上依赖于其初始解，所以下面用改进的最近邻算法求初始解，以得到更优的结果。
改进的最近邻算法：M：表示未安排路线的客户集合；s：用以累加一条路径上客户点的需求量；r：存储一条未完成路径其车辆的容量与其当前最后一个节点处需求量的累加值s之差；M''：存储本文讨论问题中一个解的全部路径；lujing：存储当前要生成的路径，如果生成完毕，将其加入到M''中；j：存储当前未完成路径中的最后一个节点；i：存储当前M中被选中要为其安排路线的那个点。
第一步：初始化。令M←1，…，N，s←0，M''←？覫，lujing←？覫。
第二步：当M≠？覫时，重复以下步骤，否则，算法结束，输出M''。
本文的问题要求油耗尽量小，为了实现这一目标，在改进的最近邻算法中生成一条新的路径时，在未安排路线的节点中选取其需求量与它到当前未完成路径的最后一个节点（如果当前未完成路径为空时，其最后一个节点为车场）的距离之比最大或次大者进行添加，这样很明显可以降低油耗。
3.2 禁忌算法中解的表示
由于上述问题为多车型单车场问题，本文用MATLAB实现该禁忌搜索算法，为了便于进行邻域操作，所以采用车型代替车场，用一维元胞数组来表示问题的一个解，例如，设一车场共有3种类型的车辆，该车场为10个客户完成送货任务，则可以用1，2，3表示三种车型，1～10表示10个客户，则一维元胞数组：
{[5]， [2，2，5]， [3，1，4，10]， [1，3]， [2，7，9]， [1，6，8]}
表示问题的一个解其含义如下，此解共有5条路径：第一条路径：第2种类型的一辆车从车场出发到达客户2，再由客户2出发到达客户5结束；第二条路径：第3种类型的一辆车从车场出发到达客户1，再由客户1出发到达客户4，再由客户4出发到达客户10结束；第三条路径：第1种类型的一辆车从车场出发到达客户3结束；第四条路径：第2种类型的一辆车从车场出发到达客户7，再由客户7出发到达客户9结束；第五条路径：第1种类型的一辆车从车场出发到达客户6，再由客户6出发到达客户8结束。
3.3 禁忌算法中邻域操作
由于本文问题中车辆具有不同的类型，加上要减少车辆的启动费用，所以下面采用一些特殊的邻域操作来减少所使用车辆的剩余容量以及减少所使用的车辆的数目。
随机从M''（其含义同改进的最近邻算法中的M''）中取两条路径，再分别从两条路径中取出两个节点：
（1）如果两节点均为车型，则分别将取出的两路径的车型更换成容量与其路径装载量（该路径上所有客户点需求量之和，以下同）最近的车型。
（2）如果两节点一点为车型，一点为客户点，将客户点插在另一路径的车型之后，并在原路径中将其清除，如果清除客户点之后此路径中还有客户，就将此两条路径的车型更换成容量与其装载量最近的车型。如果清除客户点之后这条路径已经没有客户，则将其在M''中删除，只将另一条路径的车型更换成容量与其装载量最近的车型。 （3）两节点均为客户点，将第二个客户点插在第一个客户点之后，并在原路径中将其清除，如果清除客户点之后此路径中还有客户，就将此两条路径的车型更换成容量与其装载量最近的车型。如果清除客户点之后这条路径已经没有客户，则将其在M''中删除，只将另一条路径的车型更换成容量与其装载量最近的车型。
3.4 禁忌算法中评价值的计算
3.5 禁忌搜索算法中禁忌对象、禁忌长度
本文所选的禁忌对象及禁忌长度参照文献[14]。
4 例子
对此例而言，禁忌搜索算法对初始解的改善是很明显的。
5 结 论
本文针对带油耗的单车场多车型车辆路径问题采用禁忌搜索算法进行求解，提出了改进的最近邻法求初始解，此算法可以降低油耗，在禁忌搜索算法中为了减少所派遣车辆的剩余容量和所派遣的车辆数而采用了一些特殊的邻域操作，算例表明该算法易于实现，且效果较好。本文为单车场问题，而对于多车场问题我们将进行下一步研究。
参考文献：
[1] Dantzig G.. B.， Ramser J. H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80—91.
[2] 杨文霞，郭海湘，杨娟，等. 改进的扫描法求解单车场多车型车辆路径问题[J]. 物流技术，2010，4（215）：50—53.
[3] 贾立双，李静. 基于一种改进算法的单车场多车型车辆调度研究[J]. 中国制造业信息化，2008，37（19）：8—10.
[4] 洪波，郎茂样. 多车型配送车辆调度问题的模型及其禁忌搜索算法研究[J]. 长沙交通学院学报，2005（3）：73—77.
[5] 钟石泉，贺国光. 多车场车辆调度智能优化研究[J]. 华东交通大学学报，2004（6）：25—29.
[6] Oberlin P.， Rathinam S.， Darbha S. A Transformation for a Multiple Depot， Multiple Traveling Salesman Problem[C]. American Control Conference， 2009：2636—2641.
[7] Sariklis D， Powell S. A heuristic method for the open vehicle routing problem[J]. Journal of the Operational Research Society， 2000，51：564—573.
[8] 符卓. 开放式车辆路径问题及其应用研究[D]. 长沙：中南大学（博士学位论文），2003.
[9] 段风华，符卓. 有软时窗多车场开放式车辆路径及其禁忌搜索[J]. 计算机工程与应用，2008，44（36）：42—44.
[10] 钟石泉，杜纲，贺国光. 有时间窗的开放式车辆路径问题及其遗传算法[J]. 计算机工程与应用，2006，34：201—204.
[11] 孙国华. 带软时间窗的开放式满载车辆路径问题研究[J]. 船计算机工程与应用，2011，47（17）：13—17.
[12] 熊浩. 多车型车辆共享的MDVRP问题及其遗传算法[J]. 华中师范大学学报，2010，44（1）：29—32.
[13] Tang J. F.， Zhang J.， Pang Z. D. A scatter search algorithm for solving vehicle routing problem with loading cost[J]. Expert Systems with Applications， 2010，37（6）：4073—4083.
[14] 冯芳媛，张丽华，李阿慧. B2C电子商务中带退货的多配送站点车辆路径优化问题研究[J]. 物流科技，2011（7）：15—19.
关键词：开放式车辆路径问题；禁忌搜索算法；0—1整数规划
中图分类号：U116.2 文献标识码：A
车辆路径问题（Vehicle Routing Problem， VRP）最早由Dantzing和Ramser[1]于1959年提出， 之后产生了这一问题的许多变种，例如：多车型车辆路径问题（Heterogeneous—vehicle Vehicle Routing Problem，HVRP）[2—4]；多车场车辆路径问题[5—6]；开放式车辆路径问题[7—11]等等。
针对各种车辆路径问题，大部分文献的目标函数大致由两部分组成：（1）车辆的启动费用；（2）车辆的行驶费用。首先，车行驶费用与行驶距离有关，而现实生活中，随着油价的不断上涨，在考虑车行驶费用的时候除了考虑行驶距离对于行驶费用的影响，耗油量对于行驶费用的影响也是很大的，所以熊浩[12]、唐加福[13]等人在目标函数中考虑了油耗成本对线路的影响，但是他们考虑的都是封闭式车辆路径问题。而由于各厂商现在大部分都采用物流外包，所以有必要考虑路径为开放形式的，这样更符合实际生活，故此本文考虑带油耗的开放式车辆路径问题，即：车辆在对其负责的路径上的客户进行服务时，不必回到原车场，而是终止于它所服务的最后一个客户点。另外，由于一个物流公司所服务的客户其需求不同，因此可能需要该物流公司派出不同类型的车辆对其进行服务，即使所服务的客户没有特殊要求，物流公司本身也可能具有不同型号的车辆，而不同车型的车辆其启动费和最大容量是不同的，由此会对物流公司的车辆分配方案产生影响，所以本文研究的车辆路径问题还要考虑车辆的启动费用及容量。
1 问题描述
2 数学建模
其中：（1）的第一项与第二项分别表示所有配送车辆总的油耗和总的启动费用；（2）表示所用的每类型车车数不超过此类型车数；（3）表示每个客户点恰好被访问一次；（4）表示离开每个客户点的车辆数小于或等于进入该客户点的车辆数；（5）表示被派遣的每一辆车的载重量都不超过其容量。
3 模型求解
因为开放式车辆路径问题（OVRP）是NP难的[8]，而本文讨论的问题是对OVRP的扩展，所以本文的问题也是NP难的，因此下面采用禁忌搜索算法对其进行求解。
3.1 禁忌算法中的初始解的求法
由于禁忌搜索算法求解的好坏在一定程度上依赖于其初始解，所以下面用改进的最近邻算法求初始解，以得到更优的结果。
改进的最近邻算法：M：表示未安排路线的客户集合；s：用以累加一条路径上客户点的需求量；r：存储一条未完成路径其车辆的容量与其当前最后一个节点处需求量的累加值s之差；M''：存储本文讨论问题中一个解的全部路径；lujing：存储当前要生成的路径，如果生成完毕，将其加入到M''中；j：存储当前未完成路径中的最后一个节点；i：存储当前M中被选中要为其安排路线的那个点。
第一步：初始化。令M←1，…，N，s←0，M''←？覫，lujing←？覫。
第二步：当M≠？覫时，重复以下步骤，否则，算法结束，输出M''。
本文的问题要求油耗尽量小，为了实现这一目标，在改进的最近邻算法中生成一条新的路径时，在未安排路线的节点中选取其需求量与它到当前未完成路径的最后一个节点（如果当前未完成路径为空时，其最后一个节点为车场）的距离之比最大或次大者进行添加，这样很明显可以降低油耗。
3.2 禁忌算法中解的表示
由于上述问题为多车型单车场问题，本文用MATLAB实现该禁忌搜索算法，为了便于进行邻域操作，所以采用车型代替车场，用一维元胞数组来表示问题的一个解，例如，设一车场共有3种类型的车辆，该车场为10个客户完成送货任务，则可以用1，2，3表示三种车型，1～10表示10个客户，则一维元胞数组：
{[5]， [2，2，5]， [3，1，4，10]， [1，3]， [2，7，9]， [1，6，8]}
表示问题的一个解其含义如下，此解共有5条路径：第一条路径：第2种类型的一辆车从车场出发到达客户2，再由客户2出发到达客户5结束；第二条路径：第3种类型的一辆车从车场出发到达客户1，再由客户1出发到达客户4，再由客户4出发到达客户10结束；第三条路径：第1种类型的一辆车从车场出发到达客户3结束；第四条路径：第2种类型的一辆车从车场出发到达客户7，再由客户7出发到达客户9结束；第五条路径：第1种类型的一辆车从车场出发到达客户6，再由客户6出发到达客户8结束。
3.3 禁忌算法中邻域操作
由于本文问题中车辆具有不同的类型，加上要减少车辆的启动费用，所以下面采用一些特殊的邻域操作来减少所使用车辆的剩余容量以及减少所使用的车辆的数目。
随机从M''（其含义同改进的最近邻算法中的M''）中取两条路径，再分别从两条路径中取出两个节点：
（1）如果两节点均为车型，则分别将取出的两路径的车型更换成容量与其路径装载量（该路径上所有客户点需求量之和，以下同）最近的车型。
（2）如果两节点一点为车型，一点为客户点，将客户点插在另一路径的车型之后，并在原路径中将其清除，如果清除客户点之后此路径中还有客户，就将此两条路径的车型更换成容量与其装载量最近的车型。如果清除客户点之后这条路径已经没有客户，则将其在M''中删除，只将另一条路径的车型更换成容量与其装载量最近的车型。 （3）两节点均为客户点，将第二个客户点插在第一个客户点之后，并在原路径中将其清除，如果清除客户点之后此路径中还有客户，就将此两条路径的车型更换成容量与其装载量最近的车型。如果清除客户点之后这条路径已经没有客户，则将其在M''中删除，只将另一条路径的车型更换成容量与其装载量最近的车型。
3.4 禁忌算法中评价值的计算
3.5 禁忌搜索算法中禁忌对象、禁忌长度
本文所选的禁忌对象及禁忌长度参照文献[14]。
4 例子
对此例而言，禁忌搜索算法对初始解的改善是很明显的。
5 结 论
本文针对带油耗的单车场多车型车辆路径问题采用禁忌搜索算法进行求解，提出了改进的最近邻法求初始解，此算法可以降低油耗，在禁忌搜索算法中为了减少所派遣车辆的剩余容量和所派遣的车辆数而采用了一些特殊的邻域操作，算例表明该算法易于实现，且效果较好。本文为单车场问题，而对于多车场问题我们将进行下一步研究。
参考文献：
[1] Dantzig G.. B.， Ramser J. H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80—91.
[2] 杨文霞，郭海湘，杨娟，等. 改进的扫描法求解单车场多车型车辆路径问题[J]. 物流技术，2010，4（215）：50—53.
[3] 贾立双，李静. 基于一种改进算法的单车场多车型车辆调度研究[J]. 中国制造业信息化，2008，37（19）：8—10.
[4] 洪波，郎茂样. 多车型配送车辆调度问题的模型及其禁忌搜索算法研究[J]. 长沙交通学院学报，2005（3）：73—77.
[5] 钟石泉，贺国光. 多车场车辆调度智能优化研究[J]. 华东交通大学学报，2004（6）：25—29.
[6] Oberlin P.， Rathinam S.， Darbha S. A Transformation for a Multiple Depot， Multiple Traveling Salesman Problem[C]. American Control Conference， 2009：2636—2641.
[7] Sariklis D， Powell S. A heuristic method for the open vehicle routing problem[J]. Journal of the Operational Research Society， 2000，51：564—573.
[8] 符卓. 开放式车辆路径问题及其应用研究[D]. 长沙：中南大学（博士学位论文），2003.
[9] 段风华，符卓. 有软时窗多车场开放式车辆路径及其禁忌搜索[J]. 计算机工程与应用，2008，44（36）：42—44.
[10] 钟石泉，杜纲，贺国光. 有时间窗的开放式车辆路径问题及其遗传算法[J]. 计算机工程与应用，2006，34：201—204.
[11] 孙国华. 带软时间窗的开放式满载车辆路径问题研究[J]. 船计算机工程与应用，2011，47（17）：13—17.
[12] 熊浩. 多车型车辆共享的MDVRP问题及其遗传算法[J]. 华中师范大学学报，2010，44（1）：29—32.
[13] Tang J. F.， Zhang J.， Pang Z. D. A scatter search algorithm for solving vehicle routing problem with loading cost[J]. Expert Systems with Applications， 2010，37（6）：4073—4083.
[14] 冯芳媛，张丽华，李阿慧. B2C电子商务中带退货的多配送站点车辆路径优化问题研究[J]. 物流科技，2011（7）：15—19.