基于干支线联合调度的D公司物流网络优化研究

杨雪键 何玉洁 刘森 刘玲

摘要：针对包含一个物流中心、多个中转站和多个终端零售客户的D公司物流网络布局，根据物流配送决策的实际过程，建立一个基于接驳点的干线-支线联合优化问题模型。干线为中转站选址与物流中心到中转站的运输；支线优化表示所选中转站的车辆分配、客户选择及配送路径问题。文章首先采用贪婪算法构建初始方案，再使用变邻域搜索算法优化初始方案，采用移除算子和交换算子等进行邻域扰动，形成使配送与运输决策更加合理的方案，有效提高了D公司的车辆利用率，降低运输成本，节省运输时间，提升整个运输环节的效率。

关键词：物流网络； 选址-路径问题； 贪婪算法； 变邻域搜索算法

中图分类号：U116.2；TP18  文献标识码：A   文章编号：1674-0688（2023）03-0117-06

0 引言

2018年12月21日，国家发展和改革委员会和交通运输部发布《国家物流枢纽布局和建设规划》，其中大理白族自治州成功入选国家物流枢纽承载城市，并布局建设商贸服务型国家物流枢纽。大理D物流公司紧抓政策机遇，以“构建智慧物流”为核心，逐步实现物流作业数字化、业务智能化，在降本增效的同时，推进商贸和物流资源的整合，优化物流网络布局，积极推进“滇西区域物流中心”建设。经过多年的发展，大理D物流公司已经建立起较为完善的零售产品运输体系，但受人工调度的局限性，运输效率并不高，存在车辆资源利用不充分、车辆载荷不均衡或路线不合理等问题，需从管理模式变革出发，利用智能算法等手段构建智能调度系统，较快、较好地实现区域化驱动资源，整合跨县级配送，从“打破行政区划，打破城乡界限，打破县级中转”入手，建设“区域中转圈”物流配送服务新模式。

在两阶段选址?路径问题中，中转仓的选址及配送路径的规划之间相互影响，中转仓的选址影响整个企业的运作效率和配送路径的规划；而配送路径的规划又影响企业运营状况和竞争力水平［1-2］。因此，整合优化大理D物流公司的中转站选址和配送路径十分必要。近年来，国内外许多学者对多级车辆运输的相关选址路径开展规划方案及方法论研究［3-8］。Jacobsen等［9］考虑选址?路径问题中多阶存在性，提出3个建设性启发式求解模型。路世昌等［10］构建了以考虑碳排放量的物流综合成本最小为目标的规划模型，并设计出两阶段启发式算法，解决配送中心选址与多车型车辆路径优化组合的决策问题。李珍萍等［11］以总成本极小化为目标，建立两层级共同配送选址-路径问题混合整数规划模型，设计求解模型的自适应大邻域搜索算法。Nguyen等［12］提出了一种多起点迭代局部搜索算法，利用禁忌搜索算法框架，并通过路径重连对解方案进一步优化。

物流网络的布局与优化问题是当前大理D物流公司的痛点，如何从全县域进行中转站选址建设、确定配送路线及客户点分配是该问题的几大难点。对此，本文建立跨县域干线—支线联合优化模型，采用贪婪思想构建初始方案，再使用变邻域搜索算法对初始方案进行优化，采用移除算子、插入算子等方法形成邻域扰动，优化运营过程，服务建设高效智能的物流智能调度系统。

1 问题描述

大理D物流公司是一家服务于大理白族自治州下辖12个县（市）的物流企业，其现有的运营模式表现为二级配送网络：物流中心—中转站—终端零售客户。该公司以政区划分为依据建设11个中转站，物流中心位于大理市，并根据客户订单的收货地址将商品分别发往11个中转站；各个中转站负责收货并完成商品在本县域配送工作。然而，受制于县域直送的配送模式，大理D物流公司逐渐显露出运输效率低、车辆资源利用不充分、车辆载荷不均衡和路线不合理等状况。并且，“一县一站”的建设使部分不宜或不必设立中转站的地区设立了多余的中转站，导致资源浪费。同时，由于未考虑到跨县域联动功能，导致各个县域间的物流配送工作存在割裂，不利于实现规模经济效应。

为解决当前大理D物流公司人工调度效率不高及资源浪费的问题，本文从大理白族自治州全域优化的角度考虑，完全打破各县域的调度模式，实现跨区域联合调度，具体做法是对中转站进行重新选址建设和功能优化，为各中转站的车辆和客户进行重新规划和分配，重新组建路线。大理D物流公司将大理白族自治州除大理市以外的11个县市划分为东、西、南、北4个区域，计划在各区域仅设置一个区域中转站。在第一级配送过程中，物流中心根据各区域客户的订单将商品分别发往4个区域中转站，每辆干线车辆只载运同一个区域的商品，车辆到达中转站以后，直接将商品卸下。在第二级配送过程中，车辆在县域联合优化的基础上重新确定客户的送货顺序，并构造每辆车的行驶路线。

本文以北域区为例，拟从洱源、鹤庆、剑川中选择一个合理的中转站，打破三县原有的配送路线，重新确定每辆车的服务客户以及规划车辆路线，目标是减少配送成本并提高配送效率。干线-支线联合优化调度运营模式图如图1所示。

2 模型建立

基于接驳点的干线-支线联合优化问题可提炼为两阶段选址-路径规划问题，即已知中心仓库（大理白族自治州物流中心）、多个候选中转站、末端客户，中心仓库到候選中转站为干线配送网络，候选中转站到客户为支线配送网络，如何进行中转点的选址，以及支线的路径规划，满足所有客户的需求且配送成本最低。

2.1 数学模型约束条件

数学模型的目标为总运输里程最短且所考虑的约束条件如下：①候选中转站选址约束；②干线车辆起始和终止位置约束；③支线车辆起始和终止位置约束；④支线客户有且仅被服务一次约束；⑤支线车辆流进出平衡约束；⑥支线车辆最大装载约束；⑦支线车辆最大工作时间约束；⑧支线车辆访问客户的前后时间关系约束。

2.2 符号说明

数学模型中的各个符号说明见表1。

2.3 数学模型建立

数学模型中涉及公式如下：

以上公式中，目标函数（1）表示最小化总配送成本（按箱公里结算）；约束（2）表示候选中转站只能选择其中的一个；约束（3）界定了干线网络车辆出发时间和到达候选中转站时间的关系；约束（4）界定了干线网络和支线网络之间的时间衔接约束；约束（5）界定了如果候选中转站s不被选中，其车辆不访问任何客户；约束（6）和（7）保证每辆候选中转站s中的车从中转站s出发执行任务，完成任务后返回到候选中转站s；约束（8）表示每个客户被服务且需求被一次性满足；约束（9）表示每个客户的车辆流平衡；约束（10）表示车辆k离开中转站s和到达第一个所访问客户的时间关系约束；约束（11）表示车辆k到达客户i和客户j时间关系约束；约束（12）表示车辆k访问客户i的装载平衡约束；约束（13）表示车辆k离开候选中转站s所装载成品烟数量等于其所要访问的客户需求量之和；约束（14）保证每辆车的装载能力限制；约束（15）表示每辆车的工作时间限制；约束（16）～（22）表示决策变量的取值范围约束。

3 算法设计

在大理D物流公司的干线-支线联合优化算法设计中，不仅需要考虑支线阶段车辆从中转站到各个客户的行驶距离，还需考虑干线阶段车辆从大理中心仓库到中转站的距离。本文首先采用贪婪思想构建初始方案，再使用变邻域搜索算法，采用移除算子、交换算子等进行邻域扰动，生成最终的优化方案。

3.1 贪婪算法构造初始方案

在该问题的初始解构造中，首先选择中转站集合中的第一个中转站为区域中转站，从该区域中转站开始，选择离该中转站最近的客户加到一辆车中，再选择离该客户最近的客户继续加到该车辆，并形成相应访问顺序的路径，直至该辆车满载或者达到工作时间限制时再启用一辆新车服务。当所有的客户均加到车辆中，计算当前解的成本，包括物流中心到当前区域中转站的配送距离及区域中转站所有车辆的配送距离。其次选择中转站集合中的第一个中转站为区域中转站，重复上述解的构成，形成第二个解，直至中转站集合中的所有中转站均被选择，将所有的解进行比较，选择成本最低的解作为初始优化方案。初始解构造流程如图2所示。

[输出当前路径，并生成一条新的空路径，设当前点i为0，并把i插入新路径中，更新当前车辆编号nm=nm+1，Load=0，T=0

][nz=nz+1，nc=n，n，nm=0，生成一条新的空路径，初始化i=0，Load=0，T=0][nz≤3][nc≥0][将点j插入当前路径中][将集合S中把点j移除，nc=nc-1][初始化N={0，1，2，…，n}，K={0，1，2，…，k}，其中，N代表客户集合，集合中的0代表中转站，K表示车辆集合，nc为未满足的客户数，nm为当前使用车辆的编号，Capacity为当前使用车辆的最大容量，Load为当前使用车辆的载货量，Time为当前使用车辆的最大工作时间，T为当前使用车辆己工作时间，Z={1，2，3}。Z代表中转站集合，nz为当前选中的中转站编号。初始化一条空路径。设当前点i为0。并把i插入路径中，集合S={1，2，…，n}，S代表以离当前点i的距离按从近到远的顺序进行排序的客户序列。设nm=0，即从车辆集合中的0号开始，派出车辆执行配送任务满足客户需求。设nz=1，即从中转站集合中的1号开始求解]

图2 初始解构造流程

3.2 变邻域搜索算法改进初始解

变邻域搜索算法是一种局域搜索元启发式方法，通过系统地改变邻域结构，不断探索新的邻域解来获取全局可能最优解。该算法从初始解开始，通过设计多种邻域结构进行全面搜索解空间，在每次计算过程中，通过当前邻域结构扰动当前解产生一个邻域解；若新的邻域解优于当前解，则新的邻域解取代当前解，继续在该邻域内搜索；若局部搜索得到的新的邻域解劣于当前解，则转向下一个邻域结构继续计算。达到最大邻域结构时，则停止变邻域算法的计算。变邻域搜索算法流程如图3所示。

给定一个初始解，通过点移除与重新插入的方式生成新的解，每一种点的删除方式与每一种点的插入方式构成一类邻域结构。本节分别设计了单条路径与多条路径中点的删除与插入算法，共计4类邻域结构。单路径邻域结构对当前解的改变较小，可看作集中搜索机制；多路径邻域结构则对当前解的改变较大，可看做分散搜索机制。在更换邻域的过程中，多路径邻域结构与单路径结构交替使用，为扩大搜索范围，每个邻域结构均可被重复使用。

（1）单路径中点的删除与插入。①邻域结构1：单路径中单个点的删除与插入。在当前解中，选择一条路径中的一个点移出，插入该路径中每个可行的位置，最后选择造成该路径成本最小的位置插入，即生成一个邻域解。路径成本指的是假设车辆到达该客户时形式的距离。②邻域结构2：单路径中2个点的删除与插入。在当前解中，随机选择一条路径中的2个点移出，该路径中每个可行的位置，最后选择造成该路径成本最小的位置插入。

（2）多条路径中点的删除与插入。③邻域结构3：多路径中单个点的删除与插入。在当前解中，选择一条路径中的一个点i移出，插入其余路径中每个可行的位置，计算插入后的每条路径的行驶成本之和（计算方法同领域结构1）；將点i插入造成总的路径成本最小的位置。④邻域结构4：多路径中2个点的交换。在当前解中，选择一条路径中的一个点i，将点i与其余路径中所有的点交换，最后选择造成总的路径成本最小的点交换。

4 实验结果分析

4.1 优化方案展示

选择大理白族自治州北部三县的实际运作数据作为实验数据进行测试，包括客户编号、客户需求、客户坐标、物流中心及中转站坐标、车辆大小等信息。在Visual Studio 2017软件上运行算法后，得到具体优化方案，区域中转站确定为鹤庆中转站，从区域中转站出发，每辆车的行驶距离、行驶时间、配送客户数、配送的商品数量、车辆空载率和车牌号，以及每辆车具体的配送任务均能体现在结果中（如图4所示）。

4.2 优化方案与原模式结果对比分析

4.2.1 干线成本对比

联合优化前后干线行驶距离对比情况见表2。

由表2可以看出，干线所有路线优化前行驶距离为340.36 km，优化后行驶距离为268.84 km，节省行驶距离约71.52 km，优化率达到20.01%。

联合优化前后干线行驶时间对比情况见表3。

由表3可以看出，干线所有路线优化前行驶时间为294.59 min，优化后行驶时间为229.16 min，节省行驶时间约65.43 min，优化率达到22.21%。

4.2.2 支线成本对比

联合优化前后支线行驶距离对比情况见表4。

由表4可以看出，三县所有路线优化前行驶距离为2 268.35 km，优化后行驶距离为1 683.74 km，节省行驶距离约584.61 km，优化率达到25.77%。

联合优化前后支线行驶时间对比情况见表5。

由表5可以看出，三县所有路线优化前行驶时间为7 117.52 min，优化后行驶时间为5 654.21 min，节省行驶时间约1 463.31 min，优化率达到20.56%。

联合优化前后使用车辆数及趟数对比情况见表6。

由表6可以看出，干线—支线联合路线优化前需使用车辆数为10辆，需要行驶的趟数一共为13趟，联合优化后需使用车辆数为16辆，需要行驶的趟数一共为16趟。在联合优化后，配送路线打破了行政区域的界限，以全域最优为目标，适当增加了车辆的数量和趟数，以减少迂回运输、重复运输和过远运输，虽然车辆数和趟数增加，但是行驶总距离和时间减少，实现总成本的最小化。

5 结语

文章借助数学模型与智能优化算法，对大理D物流公司的调度运营模式进行跨县域干线-支线联合优化，打破行政区划、突破城乡界限、摆脱县级中转，以全域最优为目标，统筹规划车辆配送路线，缩短车辆的行驶距离，减少迂回运输、重复运输和过远运输情况的发生，降低运输成本，提高公司的配送效率。同时，在支线配送过程中，采取甩箱模式，大幅度节省物品的装卸搬运时间，提高整个运输环节的效率，提升企业竞争力。

6 参考文献

［1］万孟然，叶春明，董君，等.考虑备灾的双层规划应急资源调度选址—路径优化模型与算法［J］.计算机应用研究，2021，38（10）：2961-2967.

［2］李航.多商品需求可拆分两阶段车辆路径问题模型与算法研究［D］.开封：河南大学，2022.

［3］Jepsen M，Spoorendonk S，Ropke S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem［J］.Transportation Science，2013，47（1）：23-37.

［4］Kechmane L，Nsiri B，Baalal A.Optimization of a Two-Echelon Location Lot-Sizing Routing Problem with Deterministic Demand［J］.Mathematical Problems in Engineering，2018（1）：1-12.

［5］Mirhedayatian S M，Crainic T G，Guajardo M，et al.A two-echelon location-routing problem with synchronisation［J］.Journal of the Operational Research Society，2019（54）：1-16.

［6］唐震霆，胡志华.针对多中心场站下两级选址路径问题的双智能集成算法［J］.大连理工大学学报，2022，62（5）：543-550.

［7］楊屹夫，孙冰，马艳芳，等.服务差异二级选址路径问题及大邻域搜索算法［J］.计算机工程与应用，2023，59（3）：282-292.

［8］李想，李苏剑，李宏.两级选址-路径问题的大规模邻域搜索模拟退火算法［J］.工程科学学报，2017，39（6）：953-961.

［9］Jacobsen S K，Madsen O.A comparative study of heuristics for a two-level routing-location problem［J］.European Journal of Operational Research，1980，5（6）：378-387.

［10］路世昌，邵旭伦，李丹.基于两阶段启发式算法的低碳物流选址-多车型路径问题研究［J］.制造业自动化，2023，45（3）：202-207.

［11］李珍萍，赵雨薇，张煜炜，等.共同配送选址-路径问题及大邻域搜索算法［J］.系统仿真学报，2021，33（10）：2518-2531.

［12］Nguyen V P，Prins C，Prodhon C.A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem［J］.Engineering Applications of Artificial Intelligence，2012，25（1）：56-71.