冯芳媛，张丽华，李阿慧（沈阳师范大学，辽宁 沈阳110034）

0 引 言

由于B2C 电子商务市场的发展在社会消费品零售总额中的比重逐年增加，使得电子商务企业之间的竞争越来越大，企业为赢取更大的效益必须不断完善其物流配送体系。然而近几年来随着电子商务的发展以及消费者维权意识的增强，使得产品退回事件趋于增多，这就要求在发展正向物流配送的同时考虑逆向物流配送，以减少因退货带来的损失，为此本文讨论了一个B2C电子商务下带退货的多配送站点车辆路径优化问题。

针对B2C电子商务下的车辆路径优化问题的研究成果较少[1-3]，而且都是研究不带退货的情形，而对带退货车辆路径优化问题，多数学者只研究了单配送中心的情形[4-8]，少数学者研究了多配送中心的情形[9-11]，但这些研究中未考虑车辆的启动费用，而且有的文献还要求送货优先于退货，本文在加入车辆启动费用的同时改进车辆的车载限制约束，极小化车辆使用数目和总的运输费用，建立了更符合实际情况的带退货的多配送站点车辆路径优化问题的模型并给出用一次禁忌搜索算法直接求解的方法。

1 问题描述

一个B2C电子商务企业在一个小区域内建有m个配送站点负责完成为n顾客配送的任务。当有客户订货（或退货）时，要求根据客户的地理位置及需求（或退货）量，在配送站点中进行选择并确定实际配送路线，完成配送订货和取回退货任务，使得总费用（包括车辆行驶费用和车辆一次启动费用）最小。

当m=1并限定配送站点的车辆数为1、各个客户只有需求时，上述问题就是旅行商问题，因此旅行商问题是本文所讨论问题的子问题。因旅行商问题是NP－hard的，所以本文的问题也是NP－hard的。

2 数学建模

假设每个配送站点的可用车辆数一定、车型一样，且每辆车仅隶属于一个配送站点；每辆车从各自所属的配送站点出发，完成配送和取货任务后装载回收的退货返回其所属配送站点；每个客户仅能由一个配送站点的一辆车服务；每个配送站点无存储量限制。

用1,2,…,m表示配送站点编号，令D=｛1,2 , …,m｝；m+1,…,m+n表示客户编号（其中既包括订货的客户也包括退货的客户，还有可能一个客户既有退货又有订货），令C=｛m+1,…,m+n｝；dij、cij分别表示i与j之间的距离和i与j之间单位距离的运输费用，（i,j∈D∪C，且当i=j时dij=0,cij=0）；qj、pj分别表示客户j（j∈C）的需求量与退货量；Ki、Ai、mi、ni分别表示配送站点i（i∈D）的车辆集合、可用车辆数、要配送的货物总量、收到的顾客的退货总量，且当i,j∈D,i≠j时Ki∩Kj=Ø；K表示所有车辆的集合；R、B分别表示每辆车的车载限制和一次性启动费用；Qjk、Pjk（k∈ K）当j∈D时分别表示车辆k在其所属的配送站点j的载货量和车辆k从其所属的配送站点j出发或返回所属的配送站点时回收的退货总量，当j∈C时分别表示车辆k到达顾客j处装载的还未配送的货物总量（不包括j处的需求量）与车辆k从其所属的配送站点出发到达顾客j处回收的退货总量（包括j处的退货量）；设决策变量为：

那么当ωi=0且k∈Ki时，有Qjk=0，Pjk=0,∀j∈D∪C；当ωi=1时，如果yjk=0,也有Qjk=0，Pjk=0,∀j∈D∪C。于是本文的问题可用下列的0－1整数规划模型描述：

上式（1）表示车辆行驶费用和车辆一次性启动费用之和，其中车辆一次性启动费用按车辆使用数量计算；（2）每个客户只能由一辆车服务且仅能服务一次；（3）保证如果客户由一辆车服务则该车恰好访问此客户一次；（4）车辆不在配送站点之间行驶；（5）每个客户属于且仅属于一个配送站点；（6）每个客户由它所属的配送站点的一辆车进行服务；（7）配送站点的总供应量小于等于其客户的需求量；（8）配送站点回收的退货总量等于其客户的所有退货之和；（9）每个配送站点的可用车辆数限制；（10）～（12）配送过程中的车载限制；（13）保证每辆车从各自的配送站点出发，完成任务后返回原配送站点；（14）若配送站点没有选用则无客户由此配送站点服务。

3 模型求解

由于本文讨论的问题是NP-hard的，所以下面给出一个禁忌搜索算法来对其进行求解。

3.1 禁忌搜索算法中求初始可行解的方法

因为禁忌搜索算法对初始解具有很大的依赖性，即最终解的质量以及收敛速度都与初始解有很大的关系，所以在本文给出的禁忌搜索算法中首先调用下面的算法1来产生一个较好的初始可行解。

算法 1：

第一步：修改文献[12]的算法对配送站点和顾客按着下列方法进行分组：

（1）针对每一个配送站点计算其可接收的货物总量=其可用车辆数×车载。

（3）取一适当的δ（0≤δ≤1），比较r（i）与δ的大小，若r（i）＜δ就称点i为非临界点，否则称点i为临界点。

（4）对非临界点的分派如下：①将所有非临界点客户按r（i）从小到大进行排列；②将各个配送站点总的配送量和总的回收量都赋值为空；③按着①的顺序对每一非临界点客户执行下列操作：a将各个配送站点按与该非临界点客户的距离由小到大顺序排列；b按a的顺序寻找第一个满足下列条件的配送站点：这个配送站点原来总的配送量+要分派的这个非临界点客户的需求量不超过它所拥有的车数×R，并且它原来的总回收量+要分派的这个非临界点客户的退货量不超过它所拥有的车数×R，将该非临界点客户分配给它，更新这个配送站点总的配送量=原来总的配送量+要分派的这个非临界点客户的需求量，总的回收量=它原来的总回收量+要分派的这个非临界点客户的退货量。

（5）对临界点的分派如下：将所有临界点顾客按需求量与退货量的和从大到小排列，若同时存在几个客户的需求量与退货量之和相等，则按r（i）从小到大的顺序将这些客户进行排列，之后按此顺序依次对它们执行对非临界点分派的③中的a与b操作。

注：对非临界点而言，最近距离与次近距离相差较大，所以对其分派主要考虑的是距离，而对临界点而言，最近距离与次近距离相差较小，所以对其分派主要考虑的是运量。

由此可得到一种分派，每个被选的配送站点都有一组要服务的顾客且能够满足其服务的顾客要求。

第二步：将文献[12]的C-W节约算法进行修改来实现对每个配送站点和其服务的顾客进行路径优化，其过程如下：

（1）计算节约值s（i,j）=di0+d0j－dij，令M=｛s（i,j）＞0|i,j∈C∪D,i≠j｝。

（2）在M内按s（i,j）从大到小的顺序排列。

（3）若M=Ø，终止，否则对M中第一项s（i,j）考察对应的（i,j），若满足下述条件之一就转（4），否则转（7）：

①点i与点j均不在已构成的线路上；

②点i或点j在已构成的线路上，但不是线路的内点（即不与车场相连）；

③点i与点j位于已构成的不同线路上，均不是内点，且一个是起点，一个是终点。

（4）计算点i与点j连接后线路上的总需求量Qi与总退货量Pi，若Qi≤R且Pi≤R，（R为车载）转（5），否则转（7）。

（5）从起始点（配送站点）开始依次计算车辆到达线路上每一个客户点时的装载量（装载量的计算方法为：起点的装载量为整个线路上所有客户的配送量之和，而线路上各个客户处的装载量为线路上该客户紧前点的装载量-该客户的配送量+该客户的退货量），若满足车载限制则转（6），否则转（7）。

（6）连接点i和点j。

（7）令M=M－s（i,j），转（3）。

3.2 禁忌搜索算法中解的表示方法

本文参考文献[13]给出求解带退货的多配送站点车辆路径优化问题一种新的解的表示方法，下面举例对该方法进行说明：假设有3个配送站点，6个顾客的问题，若其解为x=（14711282359363），则表示：配送站点1：可用车辆数为2辆，第一辆车的行驶路线为1-4-7-1；第二辆车行驶路线为1-1即未使用；配送站点2：可用车辆数为1辆，行驶路线为2-8-2；配送站点3：可用车辆数为2辆，第一辆车的行驶路线为3-5-9-3；第二辆车行驶路线为3-6-3。由此种解的表示方法既可以表示出每辆车的行驶路线又可以表示出每个配送中心拥有的可用车辆数目，所以是一种有效的表示方法。

3.3 禁忌搜索算法中的邻域结构

本文针对多配送中心车辆调度问题的特点对顶点重新指派法[14]进行改进，按此方法实施邻域操作可以实现线路的调整与合并。改进后的顶点重新指派方法步骤为：随机从解中选取两个节点，按如下情况进行操作：若所选的两个节点均为配送中心，则不进行节点间的重新指派；若所选的两个节点均为客户，则将第二个节点从其线路中取出并插入到所选的第一个节点的位置之前；若所选的第一个节点为客户，第二个节点为配送中心，那么如果第二个节点的紧前点为异于该配送中心的其它配送中心，则不进行节点间的重新指派；否则，将第一个节点从其线路中取出并插入到所选的第二个节点的位置之前；若所选的第一个节点为配送中心，第二个节点为客户，此时需分情况讨论：（1）若第一个节点为总线路的起点，则不进行节点间的重新指派；（2）若第一个节点的紧前点为异于该配送中心的其它配送中心，则不进行节点间的重新指派；否则，将第二个节点从其线路中取出并插入到所选的第一个节点的位置之前。

3.4 禁忌搜索算法中解的评价

本文所研究的模型因为车辆行驶具有启动费用，而一般认为启动费用是一个非常大的数，多用一辆车所增加的启动费用要远远大于其总行驶路程缩短而带来的节省，因此将极小化车辆使用数目作为第一目标，极小化车辆行驶费用作为第二目标[14]。为了充分对解空间进行搜索，接受导致不可行解的邻域变换，当违反了车辆装载能力限制时，其不可行性的程度可以引进一个惩罚值将该约束条件包含到目标函数中去进行度量，为此设p为惩罚因子，在本文中令，用E（x）表示对给定的解x的不可行程度实施惩罚的量，其计算方式如下：若x中共有ux条线路不可行，则，设x对应的目标函数值为fx，那么解x的评价值等于p×E（x）+fx。

3.5 禁忌搜索算法中禁忌对象、禁忌长度、候选集合以及终止准则的确定

本文将每次迭代得到的局部最好解（评价值最小）localbestjie（不一定可行）作为禁忌对象放入禁忌表中；取禁忌长度为一个常数l，其值根据问题的规模来确定；将从当前解的邻域中随机选择N个邻居作为候选集合；采用迭代指定步数T的终止准则。

禁忌搜索算法：

步骤1：初始化：为dij（i,j∈D∪C）、qj,pj（j∈C）、K、T、l、N、p赋值，调用上面的算法1求得一个初始可行解x0，初始化禁忌表H←｛x0｝，令迭代步数t←0；用localbestjiezhi记录localbestjie的评价值，用Sbest与Ebest分别记录次优可行解和其目标函数值，并令Sbest←x0，Ebest←x0的评价值；M是所有解的评价值的一个上界，令，x记录每次迭代时用于实施邻域操作的解，并令x←x。0

步骤2：当t＜T时重复下列操作，否则转步骤3：

（1）localbestjie←Ø，localbestjiezhi←M；n←1。

（2）当n＜N时重复下列操作，否则转（3）：

①对x用顶点重新指派法实施邻域操作，得到x的一个邻居x'；

②对x'执行下列操作：若x'∉H，求x'的评价值，若x'的评价值小于localbestjiezhi，令localbestjie←x'，localbestjiezhi←x'的评价值，n←n+1转①，否则令n←n+1转①；若x'∈H，令n←n+1转①。

（3）若 localbestjiezhi≥Ebest转（4），否则令 Sbest←localbestjie；Ebest←localbestjiezhi转（4）。

（4）如果禁忌长度＜l将localbestjie放在禁忌表的末尾，令x←localbestjie，t←t+1转步骤2，否则将禁忌表的第一个元素解禁，之后将localbestjie放在禁忌表的末尾，令x←localbestjie，t←t+1转步骤2。

步骤 3：输出Sbest和 Ebest。

4 计算实例

假设某一B2C电子商务企业在某一区域内建有3个配送站点，其中第一个配送站点拥有2辆车，第二个配送站点拥有3辆车，第三个配送站点拥有2辆车，每辆车的车型都一样载重都为10吨，某一时刻有17个需要服务的顾客，客户的需求量或退货量以及点对之间的距离分别如下面的表1和表2所示。要求在配送站点中合理选择车辆并安排行驶路线使总费用最小。

表1 各客户点的需求量和退货量

用禁忌搜索算法进行求解，其中迭代步数取400，每次迭代共搜索当前解的40个邻居，禁忌长度取5，车辆一次启动费用为300，在本例中设单位距离的运输费用cij=1,i,j∈｛1,2 , …,20｝。

应用算法1得到初始可行解及其目标函数值分别为：

用禁忌搜索算法求得的可行解及其目标函数值分别为：

由此例可以看出，禁忌搜索算法对初始可行解的改进效果是比较明显。

5 结 论

本文对带退货的多配送站点车辆路径优化问题进行了描述，为求解该问题提出了一种新的解的表示方法和邻域变换，从而构造了直接求解带退货的多配送站点车辆路径优化问题的禁忌搜索算法，该算法具有良好的寻优性能，所设计的解的表示方法直观且操作简便，易于理解。此外为了更符合B2C电子商务的经营特点可加入时间窗约束，我们将下一步对其进行研究。

表2 各点对之间的距离

[1]李维健.B2C电子商务模式下物流配送路径优化问题研究[D].北京：北京交通大学（硕士学位论文），2006.

[2]许志生.B2C网上超市与敏捷配送相结合的新零售模式研究[D].镇江：江苏大学（硕士学位论文），2010.

[3]蒋忠中，汪定伟.B2C电子商务中物流配送路径优化的模型与算法[J].信息与控制，2005,34(4):481-485.

[4]隆颖.用遗传算法求解带同样取货的车辆路径问题[J].辽宁师专学报：自然科学版，2005,7(3):86-88.

[5]郭伏，隆颖.带时窗同时取货的车辆路径问题的算法[J].东北大学学报，2006,27(5):575-578.

[6]胡天军，程文科.带回程取货的逆向物流车辆路径建模及蚁群算法[J].交通运输系统工程与信息，2010,10(3):110-114.

[7]Zhang H.G.,WU Y.X..Study on the model and improved immune algorithm for vehicle routing problem with backhauls[C]//International Conference on Computing,Control and Industrial Engineering,2010:371-374.

[8]Shu C.L.,Chich H.C..A heuristic method for the vehicle routing problem with backhauls and inventory[J].Journal of Intelligent Manufacturing,2009,20:29-42.

[9]Fan J.H.,Wang X.F.,Chen Q.S..A heuristic algorithm for multiple depots vehicle routing problem with backhauls[C]//Fourth International Conference on Fuzzy Systems and Knowledge Discovery,2007.

[10]Ren C.Y.,Wang X.B..Study on improved hybrid genetic algorithm for multi-depot vehicle routing problem with backhauls[C]//International Conference on Artificial Intelligence and Computational Intelligence,2009:347-350.

[11]Ren C.Y.,Wang X.B..Study on hybrid genetic algorithm for multi-type vehicles and multi-depot vehicle routing problem with backhauls[C]//Second International Conference on Intelligent Computation Technology and Automation,2009:197-200.

[12]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2001.

[13]郎茂祥，胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报，2004,18(1):81-84.

[14]符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J].系统工程理论与实践，2004(3):123-128.