改进的C-W算法在VRP中的应用

改进的 C-W算法在 VRP中的应用

刘乃增 闵旭东

临沂市交通运输局 山东临沂 276000

摘要：根据对现实问题的分析，提出了具有载重和体积约束的车辆路径问题的数学模型，通过对节约算法的总结分析，指出原算法的不足，然后提出一种新的改进节约算法，并用改进算法来解决具有载重和体积约束的车辆路径问题，取得了良好的效果。

关键词：车辆路径问题；节约算法；重量；体积；

1 车辆路径问题的描述

车辆路径问题（Vehicle Routing Problem,简称VRP）是物流配送优化中的一个重要问题，是由G.Dantzing和J.Ramser于1959提出的一个典型的组合优化问题，是交通和物流配送领域的一个核心问题，其典型定义如下：一般指对一系列的客户点，组织适当的行车路线，使车辆有序的通过他们，在满足一定的约束条件下（如货物需求量，车辆容量限制，以及到达时间限制等），达到一定的目标（如运距最短，费用最小，车辆数尽量少和客户满意度最佳等）。

2 满足体积和载重限制的有收集需求的车辆路径问题的模型

2.1 问题的提出

近年来，城市环境问题引起人们重视，特别是城市垃圾是影响市容市貌的一个重要问题，传统的处理城市垃圾的方法是用敞篷车辆运载城市垃圾，当车辆满载行驶时，一些垃圾到处飞扬，严重影响了市容市貌，所以具有封闭空间的城市垃圾运载车辆被提上日程，比如运用集装箱运输等，在考虑这类问题时，传统的只有载重限制的车辆路径问题已不能满足现状的需要，在这种现状下本文提出满足体积和载重限制的有收集需求的车辆路径问题的模型。

2.2 模型假设及参数说明

模型假设有h种物品

V: 收集点的集合；

V₀：收集点与车场的集合；

n ：收集点的总数目；

：收集点i与j之间的距离；

P_j: 顾客j的收集量，j=1……n；

V: 车辆的容量；

M: 车辆的载重量；

MD：任意路径允许的最大距离；

K: 车辆最大数量；

:第i种物品的重量；

:第i种物品的体积；

：第h种物品的密度；

;到i点为止的收货量；

决策变量：

=1.如果车辆K通过弧（i,j）,否则等于0；

y_ij:在弧（i,j）运行时，到i为止已收集的货物总量。

2.3 数学模型

目标函数：minimize Subject to:

1. j=1……n （2） j=0……n, k=0……K （3） k=0……K （4） k=0……K （5） 对任意的j不等于0

(6) i,j=0……n

(7) i,j=0……n, k=0……K (8) k=0……K (9) i,=0……n, (10) >=0 i,j=0……n

目标函数（1）寻求距离的最小值，约束(2)保证每一收集点都被服务，约束(3)保证同一辆车到达并离开他所服务的收集点，约束(4)保证从车场最多发出一辆车同顾客相连，约束（5）定义了最大距离限制，约束（6）定义了在j点的收集量，约束（7）定义路径的容积限制，约束(8)定义车辆载重量限制，约束（9）定义了车辆的容积限制，约束（10）重量与体积的约束。

3 节约算法

3.1 概述

节约算法是由Clarker和Wright在1964年提出的，主要用来解决运输车辆数目不确定（运输车辆数目在VRP问题中是一个决策变量）VRP问题，该算法对有向和无向问题同样有效。节约算法的核心思想是：将存在的两个回路(0,…,i,0)和(0,j,…,0)合并为一个回路(0,…,i,j,…,0)，合并操作中，整个运输问题的总运输距离将会发生变化，如果变化后总运输距离下降，则称节约了运输距离，相应的变化值称为节约距离。

3.2 研究现状

节约算法在提出以后，以其简单易用得到广泛应用，在国外的研究较多，改进方法也提出很多，涉及到时间及重量的研究，但涉及体积的研究较多；然而，节约算法在国内的应用研究较少，林晓宇在节约算法的研究中，提到载重量和体积限制的的节约算法解决车辆路径问题，但其在求总容积时，是以经验系数为基准，偏差较大，难以满足货品多样化的需要，并且，他不允许进行货物的分割，同一个收集点不允许多辆车进行服务，因此很多方面存在较大缺陷。

3.3 传统的考虑载重量的节约算法流程

首先，以车场直接往返收集点的方式作为初始可行解，然后计算收集点相互连接后的节约量，节约量按降序排列，按节约量从大到小的方式进行调整，将节约量最大的两个收集点进行连接，看货物量重量是否超过车辆的载重量，如果未超过车辆载重量，再连接节约量次之的收集点，再看是否超过车辆的载重量，如果否，连接第三个点，以此类推；如果超过车辆载重量，寻找新的车辆路径，直到所有收集点都被车辆覆盖，形成m辆车n条路径车辆路径。

3.4 具有载重量和体积约束的改进节约算法

以车场直接往返收集点的方式作为初始可行解，判断分析货物的密度，如果密度 ，我们以载重量作为车辆的衡量指标，反之，以体积作为车辆的衡量指标。假设 ，我们以载重量作为车辆的衡量指标，我们计算节约量，并将节约量进行降序排列，寻找节约量最大的两个点，计算是否超过车辆的载重量（1）如果未超过载重量，再计算是否满足车辆的体积要求，如果没有超过体积限制，寻找与这两个收集点最大的节约量，并计算体积与重量的车辆限制条件，以此类推；（2）如果链接节约量最大的两个点以后，载重量满足约束，而容量为满足约束，连接这两个点，但减少体积多余部分的重量，并从车场排出新的车辆来装载这部分多余的重量，同时寻找与这个收集点有货物需求的节约量最大的点，以此类推，直到所有的点的货物量都被车辆覆盖。改进算法的优点：（1）可以将货运量进行分割，只要未超过车辆的体积与载重量的约束，按节约量的大小，车辆装载直到满足其限制要求。（2）连接形成一条新的路径后，有剩余货品的收集点与其他有货品的需求点形成一个新的车辆路径问题。

4 总结与展望

本文提出的具有载重和容积的车辆路径问题的模型以及考虑重量和体积约束的节约算法具有很高的现实实用性，丰富了车辆路径问题的研究；下一步研究的重点是考虑多目标的具有收集需求的车辆路径问题和具有时间、重量、体积的节约算法的研究。

参考文献

［1］林晓宇，李金铭，纪寿文。车辆路径问题c-w算法的改进与实现[J]。交通与计算机。2004，6（22）：72-74

［2］张学志，陈功玉。车辆路线安排的一种改进节约算法[J]。物流技术。2008，27（10）：139-141.

［3］连启里，张曦。态旅游区废弃物回收的逆向物流选址-路径问题[J]。物流技术。2008，27（11）:60-62.

［4］张玲，王朝霞。物流配送优化的模型与求解[J]。商场现代化。2006，4：126-127.

5