连锁零售企业车辆配送路径优化研究，本文主要内容关键词为：零售企业论文,路径论文,车辆论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
由于有限的仓储空间，零售业连锁店经常面临因顾客退货、商品包装和饮料空瓶等物件所带来的存储压力。因此，负责这些店面商品配送的连锁零售企业的配送中心往往专程派出车辆负责旗下各店的回收工作。但近两年，由于新型车辆（如侧卸式货车）的投入使用和逆向物流成本越来越得到企业的重视，从配送中心发出的车辆同时承担了各连锁店的送货和回收两项工作。然而，合理的配送车辆数量、车辆访问各店的顺序及车辆在各店的回收量等问题却仅仅依靠配送中心管理人员的经验来做出决策，从而导致成本的不可控和意外事件的时常发生。为此，一套相应的决策理论亟待推出，笔者就此做出了一定尝试。
一、模型描述
经典的VRP描述了从仓库开出的车队对若干已知需求的客户进行配送，最终返回仓库的过程。车队中各车辆的容量相同，并且每个客户仅被访问一次。 VRP的目标是整个车队访问路径长度的最小化。而笔者研究的问题是车辆路径问题(VRP)的变体，在送货的同时加入了取货作业。
为了便于研究，在不失真实性的原则下，做出了两方面的假设。首先，由于配送中心实际投入配送作业的车辆数可以通过各连锁店商品配送的总需求量来确定，并且车辆将被划分到不同区域完成其各自的配送任务。故假设仅有一辆已知容量的侧卸式货车为各连锁店服务，并能够在每个工作周期内满足所有连锁店的商品配送需求。其次，假定本文研究的实体均处于闭环系统中，即外界的影响（如交通阻塞或天气）将被忽略。则本文描述的问题可简化为这样一个过程：一辆容量固定的货车在装满各连锁店所需商品后从配送中心出发，对所有连锁店进行逐一访问，在停经各店时卸下该店所需商品，并回收其需返回物件。当车辆访问完所有店面后返回配送中心，即完成一个工作周期。然而，在这个工作周期内，社会车辆也将参与连锁店的配送作业来满足各店的紧急需求，这样就导致了某些连锁店回收量过大，而配送中心车辆在送货时可能无法完全回收该店需返回物件。而对于未能及时回收的需返回物件，配送中心将支付连锁店一定数额的罚金作为延迟回收的补偿。由此可见，车辆路径成本（如油耗、时间成本）和延迟回收的罚金是本文研究的问题所涉及的两大成本。
Alshamrani中研究了类似的问题，提到了车辆路径成本与罚金成本，并重点研究了延迟策略，但对两部分成本组合优化的研究还不够深入。本文研究的重点即该组合优化问题，目标为寻求最合理的车辆访问路径使车辆路径成本与延迟回收的罚金成本之和最小。规定车辆在各连锁店按照其容量尽可能多地回收该店的需返回物件，并假设仅有一种回收物件，每个工作周期内各店的计划需求量、紧急需求量和新产生的回收量是恒定的，罚款的单价是统一的。在相关模型的基础上，我们得到了本文研究问题的数学模型。
模型的相关标号如下所示：
集合
A 连锁店集合
B 所有设施集合，店1表示配送中心，B=AU｛1｝
参数
p 车辆最大容量
n 连锁店数量
m 工作周期总数
连锁店需返回物件延迟回收罚款单价
每个工作周期内连锁店i的商品需求量
连锁店i的最初需返回物件量
每个工作周期内连锁店i由于紧急需求导致的需返回物件量
连锁店i与连锁店j之间的路径成本，连锁店i，j∈A，i≠j
决策变量
二进制变量。如果车辆在工作周期k内由连锁店i直接驶向连锁店j， 
，否则，
，连锁店i，j∈A
在工作周期k内连锁店i的回收物件数量
本文研究的问题表示为：
模型的目标函数(1)的前一部分表示车辆的路径成本（由[3]得到），函数 (1)的后一部分表示回收延迟的罚金成本（通过数学归纳法可证明，[2]中有相似论证）。约束(2)和(3)保证了每个连锁店仅被访问一次。约束(4)表示该模型目标函数的第二部分是个大范围整数规划问题。根据需返回物件的数量和车辆的最大容量，车辆在各连锁店的最大回收的需返回物件数量由约束(5)与 (6)决定。
二、解法设计
由于模型的目标函数为VRP（NP—难题）与大规模整数规划问题的组合，故普通的数学解法是不可行的。本文提出了一种新的启发式算法PDPDCCS(Pickup and Delivery Procedure for Distribution Center of Chain Stores)。而该算法的核心为在求解VRP有优势的仿生算法——最大——最小蚂蚁系统(MMAS)。
MMAS模拟了蚁群寻求食物源与巢穴间最短路径的能力。蚂蚁在觅食过程中，离巢分头寻找食物，发现食物后会返回巢穴通知同伴，同时在走过的路径上留下一种被称作“信息素”的化学物质，其他蚂蚁根据路径上的信息素强弱判断其行走路径，即附着信息素强度越大的路径会被蚂蚁优先选择。算法设想当多只蚂蚁分别沿着不同的路径回巢时，长度越短的路径的信息素强度越高，其它蚂蚁选择这样路径的概率越大；被蚂蚁选择的次数越多，路径的信息素强度越高。这样便形成正反馈，使更多的蚂蚁集中到最短的路径上，从而最短路径的概况便一目了然。
PDPDCCS在MMAS中加入了送货、回收等若干信息，然后通过修改过的 MMAS（简称MMAS’）得到配送中心各工作周期内车辆对各连锁店的访问顺序，即得到了配送中心车辆配送路径安排计划，其算法的伪代码如图1所示：
MMAS’将原算法中的“城市”看作本文研究的连锁店，其相关标号如下所示：
q 使用蚂蚁的数量
第t次迭代下连锁店处蚂蚁的数量，
连锁店i与连锁店j的距离
表示连锁店i与连锁店j之间可达性的启发信息
ρ 信息素的保有率
第t次迭代下连锁店i与连锁店j之间的信息素轨迹
第t次迭代下蚂蚁k在连锁店i与连锁店j之间的路径释放的信息素
第t次迭代下蚂蚁k在连锁店i选择连锁店j的几率
MMAS’包含如下三部分：
①信息素浓度约束
在MMAS’算法的初始迭代中，各路径的信息素浓度被规定为
，在以后的迭代过程中，各路径上的信息素浓度均在
。
②信息素轨迹构造
在算法的迭代过程中，蚂蚁更倾向于离自己所在点更近、拥有需返回物件更多的连锁店作为下一个访问单元，这种访问趋势可由以下公式确定：
公式(7)中的
是蚂蚁k可选择城市的集合，α和β是信息素轨迹浓度与启发信息相对重要度的两个参数，其中的启发信息由下式确定：
Initial:parameters,variables
Input:relevant data
For ! =1 to
Build tour for each ant,using Equation(7),(8)
Choose the best ant to update the pheromone,using Equation (9)
While (search stagnation or algorithm convergence)
Vehicle routing is obtained for corresponding working period
Incorproate pickup and delivery information into the stores on the route constructed,using constraints(5),(6)
Next !
Output relevant data and vehicle routing schedule of working periods is obtained
图1 PDPDCCS算法
③信息素轨迹更新
每次迭代后，仅有一只蚂蚁对整个路径的信息素轨迹进行更新。这个更新规则为：
其中
表示迭代最优解的值。
表1 各连锁店满意度
店号连锁店满意度（×100%）店号连锁店满意度（×100%）
1
1.00
16
0.93
2
0.98
17
0.92
3
0.85
18
0.88
4
0.83
19
0.84
5
0.89
20
0.89
6
0.93
21
0.84
7
0.86
22
0.81
8
0.79
23
0.94
9
0.91
24
0.99
10 0.88
25
0.86
11 0.84
26
0.87
12 0.88
27
0.86
13 0.84
28
0.84
14 0.94
29
0.86
15 0.94
30
0.87
注：连锁店1表示配送中心
三、算例分析
为了检验PDPDCCS算法的可行性，假设各连锁店的商品需求量和需回收物件量服从泊松分布，令P=30立方米，n=29，并根据实地调查构造出一组连锁店的相关初始数据作为算法验证的输入数据。
应用Visual Basic 6.0对PDPDCCS算法进行了编译和运行，运行时采用以下参数值：m=300，=100元／立方米，=1.5元／千米，α=2，β=2，ρ=0.1，q=20，
，MMAS’在每条路径构造过程中的迭代数为10,000。
实验得到了从第1个工作周期至第300个工作周期内车辆访问各连锁店的顺序，及每个工作周期结束后各连锁店未及时回收的需返回物件的数量，并由此得到了300个工作周期内车辆的路径成本为110250元，配送中心所支付连锁店的总罚金为56305元，即总成本为166555元。由于PDPDCCS算法本身在一定程度上能够保证总成本的最小化，故本文重点考虑的不是总成本是否为最小值，而是[2]中所关注的连锁店对于配送中心为其提供回收服务的满意程度。这里，规定各连锁店的满意度为在两个临近工作周期内所有回程需求均得到满足的次数与工作周期总数的半数(150)之比，而整个连锁店对于配送中心的满意度为各连锁店满意度的算术平均值。由表1可知各连锁店的满意度，而整个连锁店满意度为88.53%，这个结果比[2]中的一般结果要好很多，从而证明了PDPDCCS对该问题良好的可行性。
四、结论
本文针对连锁零售企业配送中心车辆同时为其连锁店提供送货、回收服务的流程优化策略进行了研究，提出了问题的基本模型，并为模型提供了一种启发式算法，并通过实验，证明了该算法的可行性，从而为配送中心管理人员相应的决策提供了理论指导。
但由于作者精力所限，对该问题的求解仅提出了一种算法，还需要通过多种可行的算法对问题的模型成本与连锁店的满意度进行比较，从而得到最优的算法。