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节约算法进行修改来实现对每个配送站点和其服务的顾客进行路径优化，其过程如下：