单车辆物流配送决策模型及其遗传算法

朱 伟，徐克林，佀占华，周 娜

（同济大学 机械工程学院，上海201804）

对配装配载及配送路线优化问题的研究一直是运输组织以及运筹学关注的重点，二者既相互影响，又相互制约.为提高配送系统运作效率及服务水平、进一步降低成本，必须从系统化、集成化的角度出发，将配装配载与运输两大功能进行整合［1］.基于以上思路，本文研究并建立了单车辆配装运输决策模型 （decision-making model for single vehicle loading-transportation，SLTD）.

SLTD 研究是典型的组合优化领域的非确定性多项式难题（NP-Hard）［2］，传统的求解方法一般是优化或启发式算法，如Clarke和Wright提出的节约算法［3］，Gillett和Miller提 出 的Sweep算 法［4］，Lin提出的r-opt（r=2，3，…；r指改换的边数）算法［5］，Norback和Love研究的几何图解算法［6］，Landrieu等运用的Tabu算法［7］等，但这些算法随结点数的增加会出现组合爆炸现象.

遗传算法（genetic algorithm，GA）最早由美国Michigan大学的Holland教授于1975年提出，它是受生物进化规律启迪的概率搜索方法［8］，极强的鲁棒性和内在的并行计算机制使它不仅在旅行商问题、背包问题、图分割问题等组合优化问题中取得了很多成果［9-10］，而且在配装配载和运输问题中也有广泛应用［11-12］，但遗传算法在SLTD 中的应用尚不多见.本文用VC++6.0语言实现了求解SLTD 模型的遗传算法，实例计算表明了算法及模型的有效性.

1 SLTD 问题定义及模型建立

1.1 SLTD问题定义

SLTD 问题可定义为：有l个客户点，配送中心服务它们的配送需求，已知运输车辆的载重量限制为G，容积限制为V，以总配送成本最低和车载利用率最高为目标函数，在一定的约束条件下，确定满足配送要求的最合适的车辆数m和最佳的车辆行程线路.本文研究SLTD 模型基于如下假设：配送中心到各需求点的距离及需求点间的距离已知；客户数量及其需求量已知；各客户需求均能得到满足且每个客户只能由同一辆车服务；需求点有且只能被服务一次；客户i任务在时间窗［te，i，tl，i］内完成，其中，te，i为时间窗起点，tl，i为时间窗终点；所有货物均可配送；货物配装无需分类，亦无需采用隔离措施；配送车辆为单一车型；配送车辆均由配送中心出发且完成全部配送任务后返回出发点；线路总需求不大于运输车辆的容量；配送过程无退货产生；各道路均通畅，不考虑交通情况约束及车辆行程约束.

1.2 模型参数及决策变量

dhj（h∈I′，j∈I）表示中心至客户或客户点之间的距离；Ski表示k车服务客户i的次序；thjk（h∈I′，j∈I）表示车辆k从中心至客户或在客户点之间运行的时间；设点h是同一条线路上点i的前相邻点，车辆到达h的时间为th，车辆到达i的时间为ti，tu，h为点h的卸货时间，则ti=th+tu，h+thik，（i∈I，h∈I′）.G为运输车载重量，V为运输车载的体积.

决策变量为

1.3 SLTD 数学模型

目标函数（1）为配送成本最小，其中第1项为配送运输成本，第2项为车辆基本运营成本，第3项和第4项分别为机会成本和惩罚成本；目标函数（2）为车载重量利用率最大，目标函数（3）为车辆容积资源利用率最高.令Z′g=-Zg，Z′v=-Zv，则线性加权后的单目标函数Z可表示为：minZ=α1Zf+α2Z′g+α3Z′v，其中，α1，α2，α3是介于0～1 之间的权重系数，可用层次分析法确定，且α1+α2+α3=1.新目标函数统一为追求最小化，为叙述方便，后文称Z为服务成本.约束式（4）确保每个客户有且仅有一个车辆为其服务；式（5）表示实际参与配送的车辆数为m；式（6）为车载重量约束，保证车辆所服务客户的总需求重量不超过车载重量；式（7）为车载体积约束，保证车辆所服务客户的总需求体积不超过车辆有效容积；式（8）为车辆路线连续性约束；式（9）和式（10）限定只能有一辆车从每个客户节点进出；式（11）为时窗约束表达式；式（12）表示客户i只能分配给参与配送任务的车辆k；式（13）为支路消去约束，确保配送车辆在任何一个客户中不形成回路.

2 算法设计

由于标准遗传算法不能保证全局收敛，因此必须精心设计遗传算法的染色体结构、适应度函数、初始群体、遗传算子和控制参数，使之发挥其优越性并以较大的概率获得全局最优解［13-14］.

2.1 遗传算法应用在模型中的适应性分析

遗传算法以编码方式将搜索空间映射为遗传空间，把可能的解编码成一个向量，称为染色体或个体，通过随机方法确定起始的一群个体，称为种群，然后以生物进化为原型，通过复制、交叉和变异等操作，选择最好的染色体，如此进化下去，直至满足期望的终止条件.

遗传算法是一种应用于优化问题的启发式算法，它尤其适用于常规算法难于求解的复杂空间，自产生以来，便以其鲁棒性好，通用性强，并行计算等魅力吸引了无数学者和工程技术人员为之探讨，但同时，它也存在 “编码复杂”、“寻优和收敛受算法设计影响大”、容易出现 “早熟”和 “进化停滞”等缺点.为此，在SLTD 模型中，算法采用了以下措施：

（1）算法中嵌入配送重量、体积及配送时窗检验子程序，减小了编码的复杂程序；

（2）实验优化算法设计，确保其对于寻优和收敛的 “正效应”；

（3）通过最佳保留和自适应交叉变异等策略改善 “早熟”和 “进化停滞”现象.

2.2 染色体结构

图1 染色体结构示意图Fig.1 Diagram of chromosome structure

图1染色体结构中，子路径内部有序即调整子路径中需求点位置，目标函数值会发生变化；子路径之间无序，即交换子路径位置，目标函数值不发生变化.

2.3 初始种群

配送中心是车辆的出发点和返回点，所以基因编码应始终以配送中心编号0开始；其次，生成l个需求点的随机序列，如i1，i2，…，il，在此序列中插入虚拟配送中心点0，具体方法如下：若且，其中，gkj表示第k条路径上第j个客户点的需求质量，vkj表示第k条路径上第j个客户点的需求体积；te，r≤tr≤tl，r，则将r至l的基因逐一向后移动1位，使r位空出，将0 插入第r位（r＜l）.接着若且且，重复如上操作，使s位空出，将0插入第s位.如此继续，直到将m-1个0全部插入染色体为止，这样就构成了一条初始染色体.如此反复，直到生成满足种群规模要求的染色体数目.

2.4 适应度函数

适应度函数是判断解个体优劣的重要手段，是解值逐步优化的驱动力.为满足适应度函数的非负要求，目标函数通过变换fi=αZbest／Zi转化为适应度函数，此处，fi为染色体i的适应度，α为常数，Zbest为当代最好染色体的服务成本，Zi为染色体i对应的服务成本.显然由表达式fi=αZbest／Zi得到的染色体适应度值越大越好.

2.5 遗传算子

选择算子：采用最佳保留的轮盘赌法复制染色体.

交叉算子：由于基因编码组间无序，组内有序的特点，如果直接采用传统的k值交叉方式，即随机选取交叉点，交换父代的相应基因片段，将可能分割已形成的优良子路径，甚至得到问题的不可行解.为此，本文采用文献［15］中的交叉算子——最大保留交叉算子运算.具体过程为：（1）如果染色体交叉点处的2个基因都为0，直接进行部分匹配交叉运算（PMX）；（2）如果染色体处的两个基因不全为0，则将交叉点左移（右移），直到交叉点处的两个基因都为0，再进行PMX 运算.如：

父代1 0120｜345｜06780

父代2 0137｜026｜50480

｜｜内为匹配段，经过最大保留交叉运算后，结果为：

子代1 013402650780

子代2 017034502680

变异算子：采用2点交换作为遗传算法的变异算子，随机选取染色体上的两个基因位，交换这两个位置上的相应基因，形成新个体.若基因串中出现连续0编码，则表示参与配送任务的车辆数多，此时应减少配送车辆，这对于优化配送车辆数目和配送线路非常重要.

2.6 交叉变异率及终止条件

（1）自适应调整交叉率pc和变异率pm：以fmax表示某代最优染色体的适应度；favg表示同代群体的平均适应度；fm表示变异染色体的适应度；fc表示两交叉个体的较大适应度值，得到：

其中，k1，k2为常数，且满足0＜k1＜k2＜1.

（2）算法终止条件：设置进化代数作为算法终止的判断条件.

2.7 算法实现步骤

步骤1 输入需求重量集N（g）=（g1，g2，…，gl），体积集N（v）=（v1，v2，…，vl），运输车载重量G和体积V，初始车辆数m；

步骤2 构造染色体；

步骤3 令Vms=0，Gms=0，这里Vms和Gms分别表示车辆m已装载的货物总体积和总重量；

步骤5 计算客户i需求量的容重比ci=vi／gi；

步骤6 找出使得min|Rm-ci|的客户i；

步骤7 比较客户i货物重量和体积与车辆剩余载重量和容积的大小，若Vi≤V-Vms且Gi≤GGms，转步骤8，否则，删除该染色体，转步骤2；

步骤8 若ti∈twi，转步骤9，否则，删除该染色体，转步骤2；

步骤10 若Im=Φ，转步骤11，否则转步骤4；

步骤11m=m-1；

步骤12 若m≥1转步骤3，否则，确认该染色体生成；

步骤13 重复步骤2～步骤12，直至生成满足规模要求的染色体数目；

步骤14 设置控制参数（种群规模n、交叉率pc、变异率pm及最大迭代次数T）；

步骤15 gen=0，产生初始群体p（0），群体中每条染色体表示一个SLTD 方案；

步骤16i=1；

步骤17 将群体p（gen）中的第i条染色体译成服务成本；

步骤18 计算第i条染色体的适应度值；

步骤19i=i+1；

步骤20 若i≤n，则返回步骤17.否则，染色体复制；

步骤21 进行最大保留交叉、2点变异；

步骤22 gen=gen+1，若满足终止条件则停止，否则转步骤16.

3 实例计算与分析

3.1 实例计算

某自有型配送中心服务8 个客户的货物配送，配送中心与客户依次编号为0，1，…，8，各客户的货物需求量和需求体积、服务时窗及卸货时间由表1给出.配送任务由载重量为8t，容积为10m3的车辆执行，配送中心与客户点及各客户点之间的距离由表2给出（假设dij=dji，dii=0）.取c1=2，c2=4，车辆平均行驶速度为60km·h-1，确定完成任务的车辆数及行车路线.

表1 客户需求特征Tab.1 Characteristics of customer demand

3.2 结果分析

配送中心用3辆车即可完成配送任务，3车辆的线路分别为0→6→7→5→0，0→3→4→0，0→1→2→8→0；其配送线路长度分别为357，318和312km；服务成本分别为946，849和834元；载重利用率分别为85%，86%和90%；容积利用率分别为85%，87%和84%.图2为配送结果柱状图.

表2 网点间距离矩阵Tab.2 Distance matrix of node km

图2 配送结果柱状图Fig.2 Column map for distribution results

4 结束语

采用遗传算法实现了SLTD 模型的求解，本方法可有效地节约车辆行程，降低服务成本；使车辆的载重量和容积资源得以充分利用，减少配送车辆数目，降低配送车辆的购置费用.通过对遗传算子的改进及约束检验子程序的嵌入，算法于全局搜索，改善了局部收敛及早熟现象且提高了算法的速度及解的精准度，较好地解决了多目标配装运输决策问题.下一步将对多车配送及配送与回收集成问题进行研究.

［1］ Tuzun D，Burke L I.Atwo-phase tabu search approach to the location routing problem［J］.European Journal of Operational Research，1999，116（1）：87.

［2］ Mosheiov G.The travelling salesman problem with pick-up and delivery［J］.European Journal of Operation Research，1994，79（2）：299.

［3］ Clarke G，Wright J W.Scheduling of vehicles froma central depot to a number of delivery points［J］.Operations Research，1964，12（4）：568.

［4］ Gillett B，Miller L.A heuristic algorithm for the vehicle dispatch problem［J］.Operations Research，1974，22（2）：340.

［5］ Lin S.Computer solutions of the traveling salesman problem［J］.Bell System Technology Journal，1965，44（10）：2245.

［6］ Norback J P，Love R F.Geometric approaches to solving the traveling salesman problem［J］.Management Science，1977，23（11）：1208.

［7］ Landrieu A，Mati Y，Binder Z.Atabu search heuristic for the single vehicle pickup and delivery problem with time windows［J］.Journal of Intelligent Manufacturing，2001，12（5-6）：497.

［8］ Holland J H.Adaptation in natural and artificial system［M］.Ann Arbor：The University of Michigan Press，1975.

［9］ Grefenstette J，Gopal R，Rosimaita B，et al.Genetic Algorithms for the traveling salesman problem［C］／／Proceedings of the 1st International Conference on Genetic Algorithmand Their Applications.Pittsburgh：Lawrence Erlbaum，1985：160-168.

［10］ 王蕾，沈庭芝，招扬.一种改进的自适应遗传算法［J］.系统工程与电子技术，2002，24（5）：75.WANG Lei，SHEN Tingzhi，ZHAO Yang.An improved adaptive genetic algorithm ［J］.Systems Engineering and Electronics，2002，24（5）：75.

［11］ Montano B R，Anandalingam G，Zandi I.A genetic algorithmapproach to policy design for consequence minimization［J］.European Journal of Operational Research，2000，124（1）：43.

［12］ 谢秉磊，孙毅，李荣喜.求解配送＼收集旅行商问题的遗传算法［J］.陕西工学院学报，2002，18（1）：70.XIE Binglei，SUN Yi，LI Rongxi.Genetic algorithm solving salesman problem with pickup and delivery［J］.Journal of Shaanxi Institute of Technology，2002，18（1）：70.

［13］ 周明，孙树栋.遗传算法原理及应用［M］.北京：国防工业出版社，2002.ZHOU Ming，SUN Shudong.Genetic algorithm theory and application ［M］. Beijing： National Defence Industry Press，2002.

［14］ 玄光男，程润伟.遗传算法与工程设计［M］.北京：科学出版社，2000.XUAN Guangnan，CHEN Runwei.Genetic algorithms and engineering design［M］.Beijing：Science Press，2000.

［15］ 李军，谢秉磊，郭耀煌.非满载车辆调度问题的遗传算法［J］.系统工程理论方法应用.2000，9（3）：236.LI Jun，XIE Binglei，GUO Yaohuang.Genetic algorithm for vehicle scheduling problem with non-full load［J］.Systems Engineering—Theory Methodology Application，2000，9（3）：236.