公路零担物流企业末端配送路径优化

邓红星，王玮琦，王永康

(1.东北林业大学 交通学院，黑龙江 哈尔滨 150040； 2.中国铁路上海局集团有限公司 蚌埠货运中心，安徽 蚌埠 233000)

企业物流的高效运作关系到企业的运营与发展。物流的末端配送车辆路径优化因其节省成本、提高效率、增加企业竞争力等优点而被广泛关注，因此，研究配送体系中的车辆路径优化问题十分必要，近些年国内外学者都在努力探索。

国外对公路零担货运的研究主要集中在运输网络模型的设计。Yaman[1]提出了层级轴辐式网络设计模型，进而实现网络资源的均衡利用。Alumur[2]等在考虑建站成本和需求不确定性的基础上，构建了单分配和多分配枢纽点选址的共用模型。 Ishfaq和Sox[3]通过评估枢纽点作业对于网络设计的影响，建立了以物流网络设计成本最小化为目标的数学模型。Alan Erera[4]针对零担货运(LTL)承运商面临的服务网络设计问题提出了一个整数规划模型。

近年来，公路零担货物运输迅猛发展，引起了国内很多专家的关注，专业性的研究也越来越多。王瑞等人[5]对公路零担货运企业扩大营业网点的方式进行了SWOT分析，提出相应的发展策略。孙真[6]利用共同配送理论将城市末端物流资源进行整合，从而缓解末端物流配送成本高、效率低的问题。 莫仁边[7]通过分析电子商务平台给零担运输企业带来的挑战和机遇，就提高零担运输企业竞争力提出了相应对策。许智子和宋微等人[8-9]通过引入相关的数学模型，用以解决零担运输配送路径优化问题。田昀和罗耀等人[10-11]分别利用模拟退火算法和改进粒子群算法对配送路径优化问题进行分析研究。刘丹霞[12]构建了基于“互联网+”的同城配送路径优化模型，并使用改进的禁忌搜索算法对带时间窗的同时取送货问题进行了优化求解。吴正阳[13]建立了静态模型和动态模型，用于解决多资源约束下配送路径的优化问题。

本文从企业角度出发，根据公路零担物流企业的实际物流问题，建立数学模型，并结合算法对零担物流企业末端配送路径进行优化设计，更加具有针对性和实践意义。

1 末端配送路径优化模型的建立

1.1 问题描述

公路零担物流企业末端配送路径优化模型可以描述为：在已经获取配送中心以及客户点的地理位置信息情况下，安排一定数量的配送车辆从配送中心装载货物后出发，为客户点提供送货和集货服务，其中，车辆的最大行驶距离以及载重量己知，每个客户的可接受服务时间和需求量己知，要求合理安排配送车辆，规划合理的配送路径，在满足约束条件的前提下，实现目标函数的最优。

1.1.1 优化目标

为更加直观地表示目标优化问题，使运算过程更符合现实情况，现将路径优化模型中的目标转化为配送费用形式，包含车辆运输的固定费用和变动费用。固定费用与配送车辆的数量成正比，变动费用可以用配送距离的正比例函数来表示。

1.1.2 约束条件

在建立配送路径优化模型时，为保障配送服务的可实现性，需要设立相应的约束条件，具体可分为以下几方面：

1)货物数量约束：在优化配送路径的过程中必须使车辆遍历所有客户点。

2)送达时间约束：配送车辆只允许在约定时间段内进行装卸作业。

3)资源使用约束：在配送过程中资源使用量不能超出配送中心的现有数量。

4)配送车辆约束：由于城市内大多对货车有交通管制，只有特定的时间可以通行，并且也有载重量限制。当货物超出额定载重量时，需要增加配送车辆的数量，将配送路径进一步划分。

1.2 模型构建

1.2.1 假设条件

路径优化模型根据条件的不同可以有很多类型，根据公路零担物流企业末端配送的实际情况，对模型作出以下假设。

1)仅考虑一个配送中心对客户的配送情况；

2)配送路径与配送车辆一一对应；

3)每辆车可为多个客户服务，每个客户只能被一辆车服务；

4)客户需求的准确性和时效性必须保障；

5)地理位置及需求量均已知；

6)配送车辆车型统一且无超载现象；

7)所有货物均可同车配送有特殊要求的客户。

1.2.2 目标函数

目标函数

(1)

约束条件

∀j∈V,

(2)

(3)

(4)

(5)

Lj≥L1k-Dj+Pj-M(1-x1jk)

∀j∈k;∀k∈K,

(6)

∀i∈V;∀j∈V;i≠j,

(7)

∀j∈V;∀k∈K,

(8)

∀i∈V0;∀j∈V0;∀k∈K,

(9)

xijk∈{0，1} ∀i∈V0;∀j∈V0;∀k∈K,

(10)

∀i∈V0;∀j∈V0;∀k∈K.

(11)

式(1)以车辆运输的固定费用和变动费用最小为目标函数。式(2)确保每个顾客只能被一辆车服务。式(3)保证车辆完成对客户的服务后必须离开，以实现路径的连续性。式(4)保证每辆车从配送中心出发，到达客户后必须离开，最终返回配送中心。式(5)～式(7)为车辆载货量，分别为初始载货量、服务第一个客户后的载货量和车辆在路径中的载货量。M为一个任意大的数。式(8)为载货量条件，车辆在配送过程中不能超重行驶。式(9)为时间窗条件，确保在规定时间内完成配送。式(10)为变量的取值范围。式(11)为车辆行驶的距离不能超过额定最大距离。

文中在数学模型中出现的参数变量符号如下：V为客户集，V={2，3，…，n}；V0为节点集(客户集合和配送中心)，中心仓库由数字1表示，客户集由2，3，…，n表示，V0=V∪{1}；K为车辆集，K={1，2，…，m};Qk为车辆k的装载能力，t；Sk为车辆k的最大行驶距离，km；cd为车辆k的分派成本，元；ct为单位距离的行驶成本，元；dij为客户i和j之间的距离，km；i∈V，j∈V;i≠j;Pi为客户i的取货量，t；Di为客户i的送货量，t；ai为客户i允许最早开始服务的时间；bi为客户i允许最晚开始服务的时间；ti为客户i所需的服务时间；M为一个任意大的数；xijk为车辆k的行驶变量，xijk∈{0，1}。如果车辆k从点i(i∈V0) 行驶到点j(j∈V0)，则xijk=1，否则，xijk=0；L0K为车辆k(k∈K)离开配送中心的载重量，t；Lj为车辆服务客户j(j)后的载货量，t；Sik为车辆开始服务客户i(i∈V)的时间，如果车辆k没有服务客户i，则Sik=0。

2 基于JOPT的末端配送路径优化仿真

2.1 JOPT简介

JOPT(配送路径优化和移动资源调度算法包)是由德国DNA Evolutions软件公司开发的用于配送路径优化和车辆调度的算法包。JOPT基于遗传算法和启发规则，在解决包含大规模配送点和车辆路径问题时表现出计算速度快、优化质量高、集成方便的特点。

2.2 创建优化模型信息

1)创建模型对象信息：首先在main主程序中创建模型对象，创建云计算访问JOPT的对象Client。主要包括时间、营业时间、工作时间、资源信息、配送点信息、优化结果对象以及模型优化参数。

2)创建优化模型对象：用户需要把所有的信息都封装汇总到opt中，然后由opt上传到优化器中。

3)创建资源(人和车辆)信息：主要包括资源编号或名称、纬度经度信息、工作时间上限、行驶路程上限、工作时间区间。创建好第i个资源后，还需添加其它属性并创建多维运能变量。

4)创建配送点(客户)信息：配送点信息函数主要有配送点编号或名称、纬度经度信息、营业时间区间、资源在该配送点需要访问持续的时间(s)、该配送点被访问的优先等级(从低到高1 100)。

5)创建类对象信息：首先创建运能对象，并为运能对象添加体积约束和重量约束，然后创建装载或卸载对象，添加配送点需要装载和卸载货物的体积和重量。

6)创建数组类型信息：包括车辆工作时间、配送点开放时间、车辆资源信息、配送点信息、优化属性。

7)创建优化参数对象信息：影响整体优化执行的属性如表1所示，影响针对多目标的优化结果，可通过设置程序惩罚系数，包括总距离、最大在途距离、时间窗和载重能力来实现。

表1 优化终止条件

8)创建模型优化结果对象：可以调用的方法有总成本、总时间、总行驶时间、总行程、第i个路径的编号或名称、第i个路径上的第j个配送。

3 实例验证

淮南地区某公司有一批货物，需分别配送给26位用户(用编号A，B，C，D，…，Z表示)，车辆资源信息如表2所示，各客户需要配送的货物量、需要回收的货物量、客户点之间的位置如表3所示。按该公司现有配送方案，已知其配送成本为2 330元，配送距离为166 km，配送时间为22.2 h，使用车辆数为3辆。现利用JOPT对末端配送路径进行优化。

将JOPT算法包作为优化器，需要使用C#语言在Microsoft Visual C#2010中编写目标函数和约束条件。有以下几点需要说明：

1)车辆和人员的上班时间设置为8时至18时，行驶里程上限为800 km，工作时间上限为10 h。

2)客户点的开放时间也统一设置为8时至18时。每个客户点的作业时间设置为20 min，将客

表2 车辆资源基本信息

表3 客户点服务需求数据表

户点的优先级进行统一设置。

3)为区分配送货物和取回货物，给车辆设置运能向量，分别表示两种货物的运量和总运量，并给出各个客户点的货物类型。

4)设置迭代次数为100；设置终止条件，当目标函数值趋于稳定时，将超重惩罚系数设置为1 000。

将数据输入到visual中，运行软件，调用JOPT算法包，得到优化后绩效指标总成本为1 591元，总行驶距离为118 km，使用的配送车辆数为2辆，具体配送线路如图1所示。

根据得到的实际数据，优化前后的具体结果对比如表4所示。

表4 优化前后对比

图1 配送线路

通过以上信息可以看出，优化后的配送路径缩短了配送距离、减少了配送时间、降低了配送成本、提高了配送效率，在一定程度上增强了企业的竞争力。

4 结 语

本文运用JOPT算法包求解配送路径优化模型，对公路零担物流企业末端配送路径进行了优化。最后以末端配送的实际数据为例，证明该方法的可行性。通过对比分析，优化路径在一定程度上缩短了配送里程，降低了配送成本。因此，利用JOPT算法来优化末端配送路径的方法是可行的。本文的局限性在于仅讨论了单个配送中心同种类车辆的配送问题，但对多个配送中心的不同种类车辆配送问题还需进一步研究。