B2C电子商务中带退货的多配送站点车辆路径优化问题研究，本文主要内容关键词为：中带论文,路径论文,车辆论文,站点论文,电子商务论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
0 引言
由于B2C电子商务市场的发展在社会消费品零售总额中的比重逐年增加，使得电子商务企业之间的竞争越来越大，企业为赢取更大的效益必须不断完善其物流配送体系。然而近几年来随着电子商务的发展以及消费者维权意识的增强，使得产品退回事件趋于增多，这就要求在发展正向物流配送的同时考虑逆向物流配送，以减少因退货带来的损失，为此本文讨论了一个B2C电子商务下带退货的多配送站点车辆路径优化问题。
针对B2C电子商务下的车辆路径优化问题的研究成果较少[1-3]，而且都是研究不带退货的情形，而对带退货车辆路径优化问题，多数学者只研究了单配送中心的情形[4-8]，少数学者研究了多配送中心的情形[9-11]，但这些研究中未考虑车辆的启动费用，而且有的文献还要求送货优先于退货，本文在加入车辆启动费用的同时改进车辆的车载限制约束，极小化车辆使用数目和总的运输费用，建立了更符合实际情况的带退货的多配送站点车辆路径优化问题的模型并给出用一次禁忌搜索算法直接求解的方法。
1 问题描述
一个B2C电子商务企业在一个小区域内建有m个配送站点负责完成为n顾客配送的任务。当有客户订货(或退货)时，要求根据客户的地理位置及需求(或退货)量，在配送站点中进行选择并确定实际配送路线，完成配送订货和取回退货任务，使得总费用(包括车辆行驶费用和车辆一次启动费用)最小。
当m=1并限定配送站点的车辆数为1、各个客户只有需求时，上述问题就是旅行商问题，因此旅行商问题是本文所讨论问题的子问题。因旅行商问题是NP-hard的，所以本文的问题也是NP-hard的。
2 数学建模
假设每个配送站点的可用车辆数一定、车型一样，且每辆车仅隶属于一个配送站点；每辆车从各自所属的配送站点出发，完成配送和取货任务后装载回收的退货返回其所属配送站点；每个客户仅能由一个配送站点的一辆车服务；每个配送站点无存储量限制。
上式(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节约算法进行修改来实现对每个配送站点和其服务的顾客进行路径优化，其过程如下：
(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 禁忌搜索算法中解的评价
3.5 禁忌搜索算法中禁忌对象、禁忌长度、候选集合以及终止准则的确定
本文将每次迭代得到的局部最好解(评价值最小)localbestjie(不一定可行)作为禁忌对象放入禁忌表中；取禁忌长度为一个常数l，其值根据问题的规模来确定；将从当前解的邻域中随机选择N个邻居作为候选集合；采用迭代指定步数T的终止准则。
禁忌搜索算法：
步骤3：输出Sbest和Ebest。
4 计算实例
假设某一B2C电子商务企业在某一区域内建有3个配送站点，其中第一个配送站点拥有2辆车，第二个配送站点拥有3辆车，第三个配送站点拥有2辆车，每辆车的车型都一样载重都为10吨，某一时刻有17个需要服务的顾客，客户的需求量或退货量以及点对之间的距离分别如下面的表1和表2所示。要求在配送站点中合理选择车辆并安排行驶路线使总费用最小。
用禁忌搜索算法进行求解，其中迭代步数取400，每次迭代共搜索当前解的40个邻居，禁忌长度取5，车辆一次
由此例可以看出，禁忌搜索算法对初始可行解的改进效果是比较明显。
5 结论
本文对带退货的多配送站点车辆路径优化问题进行了描述，为求解该问题提出了一种新的解的表示方法和邻域变换，从而构造了直接求解带退货的多配送站点车辆路径优化问题的禁忌搜索算法，该算法具有更好的寻优性能，所设计的解的表示方法直观且操作简便，易于理解。此外为了更符合B2C电子商务的经营特点可加入时间窗约束，我们将下一步对其进行研究。