基于调度引擎服务的智能线路优化研究

文 / 黄 婧 李 乐 曹云祥 陈 浩 邵世洲 肖光伟 肖龙恩 周彬伟 王黎明 袁佩玲

随着全球信息化的不断发展，物流行业得到了飞速发展。由于运输业务多、车辆装载率低，物流运输费用超过了库存费用，同时由于货物及时配送服务与城市交通状况直接的矛盾，物流配送车辆路径优化成为物流系统最为关键的一环，对整个物流运输成本、效益和速度至关重要，因此如何选择最优物流配送车辆路径，及时将货物送到客户手中，成为物流研究领域中的热点问题。

物流配送车辆路径优化问题是以最少车辆数、最小车辆总行程完成货物的配送任务，从而达到成本最小或时间最短等目标。对于物流配送车辆路径问题，传统优化方法搜索时间长，难以找到最优路径，造成物流配送成本高。为了降低物流配送成本，提高车辆路径优化效率，提出一种调度引擎服务的物流配送车辆路径优化算法。首先，对物流配送车辆路径基础数据进行录入，然后建立相应的应用数据模型，最后采用调度引擎对车辆路径问题的运输场景模型进行求解。通过具体实例对算法进行试验，结果表明，调度引擎服务提高寻优效果，找到物流配送车辆路径的最优算法，降低物流配送成本，并为物流配送车辆路径选择提供了一种有效算法。

一、基于车辆配载线路优化问题的建模

1.调度引擎模型建设

物流配送车辆调度实质就是走什么样的路线进行运输的问题，其描述为：在车辆载重量和各客户需求量已知的前提下，至少派多少辆车才能满足需求且车辆的总行程最短，从而找到最小成本的配送方案，同时要去满足以下条件：

(1)每一个客户只被一辆车访问一次，每辆车只服务一条线路。

(2)所有配送车辆以配送中心为起点并最终回到物流配送中心。

(3)每条配送路径上客户需求量之和不能超过车辆的载重量。

(4)每辆车所走的路线尽量不能重复。

综上所述可知，本项目重点是解决湖北中烟的城市干线运输配送问题，湖北中烟省内共有 6 家工厂（A、B、C、D、E、F），这些工厂生产 90～100个品规的香烟，工厂间的距离在 100～600公里之间，同一个品规的香烟有可能在多个工厂同时生产。各个配送中心需要从几家不同工厂订购数量、品规各异的香烟，截单时间为每天上午9:00和下午16:00；当天9:00之前收到的所有订单均当日内完成派送处理，所以车辆在8:30左右来工厂仓库取货运走；当天16:00之后收到的所有订单将在次日处理，车辆一般在次日早上8:30来工厂仓库取货。由于车辆运输距离较长，一般路上要行驶几天才能运抵目的地。通常，从不同工厂订购不同品规的香烟，配载问题比较突出。考虑车辆的行程距离和装载量，目前车辆完成一次配载可以最多到3 个工厂仓库配载，然后将它们运送到最多 4 个配送中心。在每个卷烟厂仓库装货时，要考虑装货的先后顺序，以便到达不同客户站点卸货时能够避免倒箱操作。这样可方便用1辆车从 3 个以上卷烟厂仓库配载不同品规的香烟配送给1个配送中心，避免使用多辆车。考虑运输货值较高，因此每辆车驾驶室都安装有定位装置和摄像头，车辆行驶的实时地理位置会更新到TMS系统；TMS系统会定期维护限定司机行驶的路线，并监控司机行驶是否偏离规定路线，如出现异常偏离，给出预警信息。

烟草公司都有自己专用的地图数据库，用来规划运输调度；TMS系统可以访问烟草公司的内部地图数据库，目前该TMS系统应用华为调度引擎系统将配载站点序列信息发送至TMS系统，TMS系统根据调度引擎给出路线优化（选择可通行街道路线）的结果安排车辆调度，同时监控司机是否在指定路线上行驶。

2.线路的选择

现以多节点路线选择问题为例，将运输费用最低和运输时间最短作为目标函数，建立多目标函数的数学模型。

假设从i城市到j城市要经过M个地点节点，各地点节点有N种运输方式可供选择。在综合时效性、经济性等因素的影响下，决策出运输费用最低、运输时间最短的最优路线。数学模型以运费最低、运输时间最短作为优化目标，假设物品的运输费用为Q1，运输时间为Q2，运输时间成本为Q3，现建立如下数学模型：

①最优目录函数：Q最优=min{Q1+Q2}运输费用：

运输时间成本：Q3=δ1Q2（δ1（时间变量）≧0，运输时间不考虑在成本内时，Q3=0）

3.线路的优化

武汉物流中心A1向10个客户Ai（i=1、2、...10）配送货物，其配送网络如图1，线路上的数字表示两者之间的距离，配送中心有装载量0.3t和0.7t的车若干辆，试制定最优送货方案。

解题步骤如下：

(1)整个外围路线连线总里程：每个客户之间距离综合S=56KM

(2)该系统中所有的三角边差，如表1【例：三角边差为三角形AiA6A7中两条星型线路AiA6、AiA7之间与外围线路A6A7的差称为三角形边差（）】。

(3)由表1可以看出三角边差最小的星型三角形有三角形AiA6A7、三角形AiA7A8、三角形AiA8A9三个，因此有三种方案：

方案举例：

假设三角形AiA6A7的外围路线A6A7是断开线路，则先断开A6A7，然后按照上面所说的两个条件查找其他的断开线路，此时得方案为（图2）；

送货车辆：2（0.7t）+1（0.3t）（共3辆）；

图1 配送路线

图2 最优路径

送货线路：Ai-A3-A2-A1-A10-Ai(0.7t)、Ai-A6-A5-A4-Ai(0.7t)和Ai-A7-A8-A9-Ai（0.3t）；

线路优化的核心算法是采用基于拍卖的任务分配算法，每个任务都有一定的价值，各个小车执行不同的任务，行走的路径不同会导致执行任务代价不一。小车综合评价各个任务后，对收益最高的任务进行投标，通过拍卖的方式竞争任务的执行权，经过多轮的任务和路径优化后，最终达到分配结果的最优图，如图3。

二、基于调度引擎下的线路优化案例分析

1.数据参数输入

商品信息：卷烟成品、原料、辅料、半成品、宣传品等运输物资，其运输物资基本属性包括订单号（唯一）、装货地信息、卸货地信息、最早要求到货时间、最晚要求到货时间、运单量。

运输车辆信息：与中烟公司签订运输协议的承运商公司以及中烟公司自有的车辆。

地点信息：仓库信息、商业公司地点信息、虚拟仓库信息、分区信息（按订单运输区域划分）、仓库提货时间、商业公司营业时间等。

车辆信息：车辆类型、载重容积、最大站点数/件数、区域限制、运输商品信息等。

订单信息：商品重量体积、提卸货地点、分区信息、装卸效率、提卸货停留时间等。

计费信息：中烟公司给到的各区域计费表、承运商信息、不同商品的计费公式、吨位折算公式或标准。

表1 系统中所有的三角边差

图3 前后路径对比

表2 业务场景各种约束和调整

距离矩阵数据：需要提前准备好运输地点经纬度以及两两之间的距离数据。

2.线路规划参数设置

线路规划及优化：在考虑业务场景各种约束条件之下，以运输成本最低为目标，给到最终规划的路径，包括车次信息、各车次站点顺序、装载率、车次总体积、车次总距离、工作时长、所属区域、对应的订单信息、预计到达发货仓库时间、预计离开发货仓库时间、预计到达卸货仓库时间、预计离开卸货仓库时间。

线路调整：基于系统输出的车次，可以进行人工干预，调整车次上站点顺序、调整不同车次上运单的分配。

参数调整：根据实际业务场景，可以针对装卸货效率、沿线配载角度、提卸货停留时长、可拼载最大站点数、要求的装载率目标这些参数进行调整。

3.业务场景覆盖

单点提多点送：同时考虑到订单要求的到货时间，按沿线进行配载；考虑提卸货的停留时间和装卸效率；考虑道路的拥堵情况（设置拥堵系数），可把订单按区域进行配送；考虑超载情况。

多点提单点卸：同时考虑提卸货时间要求，按业务区域划分；考虑停留时间和装卸效率；考虑超载情况。

多点提多点送：无需考虑边提边送的业务场景；需考虑订单的提卸货时间和装卸效率；可考虑超载情况。

在上述三种场景中都支持商品和车辆的对应关系、车辆和运输地点（不一定是单个省市或者仓库）的对应、运输地点和商品的关系对应。

4.结果分析

调度引擎优化后的结果显示行程数量会减少，提升了整体资源和车载量空间的利用率，减少行驶里程和配送时间，从而降低总运输成本。一方面，我们可以查验一下针对现有行程的设定条件和验算结果是否有效；另一方面，我们还会通过下面的方法进一步降低运输成本。

调度引擎服务的优化算法可以应对订单的动态变化，比如有新订单加入、订单内容（数量/品规）变化等。如果在当天截单后又来了新订单请求，则系统会尽快确认是否可以将其添加到现有行程规划中，即使车辆已在第一个工厂取货完毕，新订单仍有机会在第二工厂取货前添加进来完成及时配载。因此，通过深层次的订单合并会进一步提高资源利用率；如果订单内容（比如装箱数量）有变化，这些信息也会及时在系统里自动更新。优化算法会自动从可用车队选择不同运输服务公司提供的最便宜车辆（依据每个站点的可用车辆信息），来降低总运输成本。

调度引擎服务提供 API 接口，用来直接集成订单和车辆数据，如，技术数据、仓库信息、区域信息、距离信息、运价规则信息、引擎接口缓存，第一次初始化后，如果没有变动，时间配载时就不需要带基础数据参数。

三、结语

合理地规划物流运输系统中车辆的线路，是提高物流企业经济效益的关键。本文针对物流配送车辆线路优化问题进行分析，针对当前存在的问题，利用调度引擎服务分析，搜索具有并行性和速度快的特点，提出一种基于引擎算法的物流配送车辆线路优化问题求解方法。通过对比试验对其进行验证，结果表明，本方法提高了寻优效率，能够快速找到最优线路，在物流配送车辆线路优化中有着广阔的应用前景。