带有外包数量折扣的多车型车辆路径问题探讨

陶 莎，朱建波，时茜茜

（南京大学 工程管理学院，南京210039）

0 引言

在物流外包服务的背景下，本文研究带有外包数量折扣的多车型路径优化问题。从车队自身角度，合理的配送方案能降低物流成本，数量折扣策略能够吸引客户和获得规模效益。随着市场竞争日益激烈，站在客户角度实现协同和双赢是物流企业得以长远发展的有效手段。车队运作管理问题通常是车辆路线问题或其扩展。VRP是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，在一定的约束下满足客户需求，达到成本和时间的最小化等目标。混合车辆路径问题[1～3]是VRP的一个扩展问题，研究为配送车队配置车辆的类型和每种类型车辆的数量以及安排各车辆的路径，使车队在成本最低的目标下完成配送任务。当车辆可变成本与车辆类型无关且每种类型车的可使用数无限大时，该问题被称为多车型车辆路径问题[4～10]。

在物流外包的背景下，本文研究具有以下新特征的FSMVRP问题，简称FSMVRPQD。一是，车辆容量和成本各不相同，外包车辆具有固定成本即外包成本；可变成本包括燃油、人力资源等成本，假定可变成本和行驶距离成正比。二是，考虑带有数量折扣的多车型车辆路径问题，并考虑时间窗、容量限制等约束。三是，根据时间窗和数量折扣的特点，本文在Liu（2009）提出的基于最短路解码的混合遗传算法基础上，通过修改适应度函数并在解码中加入时间窗条件设计求解算法。

1 问题

N={0，1，2…，n，n+1}是包含一个车库和n个客户的点集，其中0和虚拟节点n+1是车库，其它为客户节点，客户i（i∈N{0 ，n+1}）需求量为ULi，服务时间和时间窗分为为Si和[Ui，Li]。任意两节点i∈N到节点j∈N的运输距离为Di，j。车队可派出车辆的类型为TR={1，…，NT}，每类车的可用数量无限大，类型为k∈TR的车的容量（最大承载量）、平均车速和单位固定成本分别为MCk∈TR、Vk∈TR和RCk∈TR。为类型为k∈TR的车从节点i∈N到节点j∈TR的运输时间。TC为单位距离运输的运输费用。以完成n个任务的总成本f（可变成本vc与固定成本fc之和）最小化为目的，求解实际每类车的发车数量和每辆车的访问路径。类型为k∈TR的车辆的外包折扣θk与一次外包的车的数量有关，即θk(mk)。总成本包括可变成本和固定成本，可变成本直接由执行配送任务的物流外包企业承担，而固定成本（外包成本）则表示客户支付给物流企业的运输成本。本文将物流企业和客户的利益综合考虑，这有利于供应链企业间的合作，达到双赢。并且，可以考虑以下合理的现实条件：不同类型车辆的容量和固定成本不同，容量越大费用越大；每个客户只允许一辆车负责配送，即客户需求不能分割（split）；任一顾客的配送量都小于最大车型的容量；配送企业将配送任务外包给专门的配送公司，即通过外包租用所需配送能力满足物流需求。平均单量车的外包成本采取外包数量越大折扣越低的定价策略。

2 模型

式（1）表示目标是总成本的最小化，总成本包括固定成本和可变成本；式（2）计算固定成本，RCk(mk)是外包平均单位时间外包类型为k的车的费用；式（3）计算可变成本；式（4）是速度、时间和距离之间的关系表达式；式（5）表示类型为k的车离开配送中心的次数，即使用量；式（6）表示类型为k的车返回配送中心的次数。显然，车辆离开配送中心的次数等于车辆返回配送中心的次数，即所有派出车辆都要返回；式（7）和（8）对访问顺序进行约束；式（9）为基于访问顺序的卸载量约束；式（10）和（11）表示客户点的进入次数和离开次数最多为1次，即顾客点只被服务1次；式（12）表示每个顾客点的车辆进入次数等于离开次数；式（13）是时间窗约束，表示每个客户点被访问的时间必须在时间窗内；式（14）是车容量约束；式（15）为各类型车外包优惠折扣定义式，其中λ（0＜λ≤1）是折扣数，Ω为折扣限定的外包的车辆数量区间，式（15）表示外包车辆越多折扣越小，即单位车辆外包的固定成本越低。

3 进化算法

设计算法1求解上述非线性规划模型。算法1是一种进化算法，在适应度计算和解码两步骤中分别对固定成本和可变成本进行优化。算法1采用最短路径算法实现解码，解码过程详见算法2。

算法1：FSMVRPQD的进化算法

采用客户序列编码，即对客户集合{1，…，n}，染色体Ch={g(1)，g(2)，g(3)，…，g(n)} 中 n 个基因对应客户编号的一个排序。在对一个染色体进行解码时需要确定线路及其对客户的访问顺序，以及该线路对应的车辆。Liu等(2009)针对运送多种物品提出一个最短路解码方法。在该文方法的基础上，加入车辆多类型和时间窗等条件设计基于最短路径算法的解码方法。对于染色体Ch={g(1)，g(2)，g(3)，…，g(n)}，按染色体的客户编号顺序将客户划分成若干组，每组的客户由一辆配送车负责配送，要求满足每组顾客的总卸载量不能超过所选类型车的容量以及每组客户中每个客户被服务时间满足客户的时间窗要求这两个条件。并且要求该染色体对应的解是满足以上两个条件的所有方案中总可变成本最小的方案。可变成本直接采用总运输距离衡量。

首先，通过如下方式根据染色体构建一个无环有向图G。设配送车类型的编号按车容量大小升序排列，即MCk＜MCk+1，k=1，…，NT-1。对于代表一个客户序列的染色体Ch，G(Ch)是一个有向图，其节点V(G)={g(i)|1≤i≤n}，其有向边集合E(G)满足当且仅当满足式（16）和式（17）时，(i，j)∈E(G)。

即当配送车的容量约束和客户点时间窗约束均被满足时，令 (i，j)∈E(G)，k是车的类型。每条弧 (i，j)是一个可行的配送路线，表示车离开节点0（车库）且依次连续访问节点i+1，i+2，…，j。总卸货量为为类型k的车到达m节点的时刻，计算如式（17）中表示。边上权重wi，j表示为k类型车在从车库出发依次访问i+1，i+2，…，j后回到车库的运输代价。由于满足上述两个约束的车的类型可能不止一种，因此限定小型车优先。这一限定的含义是，如果上述的配送任务可以由一个容量较小的车辆完成，则其它更大容量的车就无需考虑。假定容量越小的车的固定成本越低，车速越快。在可以满足客户需求的前提下也更能节约空间（若派更大容量的车完成任务则有更大的容量浪费）。显然，优先选择成本小的车型。因此，弧上的权重通过式（18）计算，其中k=argmink{q|q∈TR，Eq.(16-17)} 。

图G(Ch)上的最短路径是对客户序列的最优划分，将其定义为染色体对应的解。为便于理解下面举一个具体的解码例子。假设有六个客户和两种车型，设染色体编码序列为Ch={g(1),g(2),g(3),…,g(n)}={2，1，6，5，4，3}图1a。图1b是相关的已知数据，弧(i，j)上的数字是距离Di，j，节点边的数字分别表示节点i的需求量（卸载量）ULi、服务时间Si和时间窗[Li，Ui]。按照上述的过程构建对应的无环有向图G(Ch)如图1c。例如弧(g(1)，g(3))=(2，6)表示依次访问节点 (0，g(2)，g(3)，0)=(0，1，6，0)的路径，先后分别计算使用类型1和类型2的车是否满足容量和时间窗的要求。计算可知类型1车不满足容量要求。而对于类型2车有：

①UL1+UL6=320+300≤900，满足容量约束；

因此，弧 (g(1)，g(3))=(2，6)∈G(Ch)可表示某一车辆的可行路径。弧对应的权重即是280+30+120=430。对于有向图G(Ch)每一条车库节点0到染色体的最后一个节点g(n)=3的路径都是满足n个客户需求车辆配置和路径选择的可行方案，其中的最短路径确保得到成本最低的方案，同时也是该染色体对应的解，如图1d所示。因此可以看出用这种方法进行染色体解码，解码后对应解的信息包括使用的车类型、数量和路径（访问的节点和依次的顺序）。

图1 染色体解码示例

编码过程较为简单，任意一个解将每辆车访问的节点按顺序串联（去掉车库0）即可编码成为相应染色体。

将上述内容总结整理，给出解码的算法2。

算法2：染色体解码算法

FSMVRPQD的优化目标是成本的最小化。采用目标值求倒数将目标函数转化为适应度函数。采用进化代数作为终止规则。

4 算例仿真

在500×500空间范围内随机生成100个需求点及其分布，设置1号点为车库，并随机生成各点的需求量（卸载量）和时间窗（时间上限、下限）。小、中、大三种车型的车速、容量、成本以及外包折扣信息如表1所示。

表1 车辆及折扣信息

在CPU为英特尔酷睿i3-380M、内存为2GB、操作系统为Windows 7的计算机上运行C#实现的算法1和算法2求解上述算例。为了研究各参数对实验结果以及运行时间的影响，设定不同的参数进行实验，在每种参数设定下运行10次，图3为实验结果及运行时间统计的对比分析图。图2中的a1、b1、c1子图分别是变异概率Pm、交叉概率Px和种群规模Ps设置不同值时的运行结果，三条折线分别是不同参数值下10次实验结果的最大值、平均值和最小值；a2、b2、c2子图分别是各参数设置下10次实验的平均运行时间。从图2可以看出，在其它参数值确定的前提下，最优成本随着Pm增大大体呈下降趋势，在设定值为0.35时，10次实验的最大、最小和平均值均最低；Px对本实验的结果没有明确的影响，随着Ps的增大，成本也大体呈下降趋势。此外，从a2和b2看出，曲线没有明显的趋势和规律，并且最大与最小的实验平均时间仅仅相差3秒和2.2秒，相对于总体平均运行时间88.22和88.34可以忽略，因此可以判断Px和Pm对运行时间均没有显著影响。图c3中直观地可以看出折线类似于一条单调上升的直线，事实上数据表明随着Ps以公差为10的等差数列递增，平均运行时间也以约100s的差值递增，可以推断运行时间与Ps大小呈正比关系。

图2 不同参数设定的实验结果及运行时间统计

根据上面的分析，综合考虑实验结果和运行时间两因素，设置各参数值为Ps=60、Px=0.7、Pm=0.35和Pg=10000，算法运行5次，平均运行时间为46分50秒，其中4次实验经过10000代进化均收敛于最优成本780，图3为4次最优实验的优化结果和进化代数的关系图。可以看出，在优化过程的开始阶段，曲线下降较快，随着进化过程的进行，曲线变化趋于平缓，但随着进化过程的进行，算法的收敛趋势明显。虽然4次实验的最优值相同，但配送方案并不相同。这是因为FSMVRPQD用外包成本衡量GA的适应度，而外包成本仅由外包车量的数量和种类决定，与车的配送路径无关。针对这一特点，当多个方案的最优值相同时，可以选择可变成本最小的方案。因此，比较4次最优实验的总行驶距离，达到最优解的代数4653的实验结果方案的总行驶距离最小，达到24177，可以选为最终配送方案。最终配送方案见表2，得到车辆总数为14，总外包成本为780。

表2 最终配送方案

图3 优化结果和进化代数关系图

5 总结

相对于典型多车型车辆路径问题的研究成果，同时考虑时间窗约束和数量折扣，是一种降低外包成本、提高车队利润和降低空载率的策略。本文建立该问题的非线性规划模型并设计基于最短路解码的进化算法，在解码过程和适应度计算过程中综合考虑车队和客户的可变成本和固定成本，是对车队和客户两方利益的整体考虑，不仅为车队提供优化的配送方案，而且降低了客户的外包成本。通过引入局部搜索方法进一步提高算法性能，考虑车辆类型对运输费用的影响、以及外包时间惩罚和折扣的影响是未来值得研究和探讨的问题。

[1]Belfiore,Pchty.Yoshizaki,Scatter Search for A Real-Life Heterogeneous Fleet Vehicle Routing Problem With Time Windows and Split Deliveries in Brazil[J].European Journal of Operational Research,2009,199(3).

[2]Brandão J.A Tabu Search Algorithm for The Heterogeneous Fixed Fleet Vehicle Routing Problem[J].Computers&Operations Research,2011,38(1).

[3]Choi E,Tchaikovsky.A Column Generation Approach to The Heterogeneous Fleet Vehicle Routing Problem[J].Computers&Operations Research,2007,34(7).

[4]Repoussis P P.Solving The Fleet Size and Mix Vehicle Routing Problem With Time Windows via Adaptive Memory Programming[J].Transportation Research Part C:Emerging Technologies,2010,18(5).

[5]Liu S Huang W,Ma H.An Effective Genetic Algorithm for The Fleet Size and Mix vehicle Routing Problems[J].Transportation Research Part E:Logistics and Transportation Review,2009,45(3).

[6]J Renaud,Boctor F F.A Sweep-Based Algorithm for The Fleet Size and Mix Vehicle Routing Problem[J].European Journal of Operational Research,2002,140(3).

[7]姜昌华,戴树贵,胡幼华.求解车辆路径问题的混合遗传算法[J].计算机集成制造系统,2007,13(10).

[8]沈玲.基于混合遗传算法的带时间窗车辆路径优化问题研究[J].物流工程与管理,2009,33(2).

[9]汪勇,丁凡,吴志华.协同进化遗传算法求解带时间窗的车辆路径问题[J].统计与决策,2010,10(1).

[10]Xu M H,Liu,Y Q,Huang Q L,et al.An Improved Dijkstra's Shortest Path Algorithm for Sparse Network[J].Applied Mathematics and Computation,2007,185(1).