联合配送车辆调度及算法实现

李伟+邓红涛+陈红莉+戴建国

摘 要：现代物流业配送模式由单一配送向联合配送、动态配送、大规模跨区域配送转化。针对这一变化，提出了一种多维协同条件下的大规模车辆调度方法，构建面向多重约束条件的车辆调度数学模型，研究了针对大规模协同配送的车辆调度算法，以达到物流调度实时化、高效化和智能化目的。

关键词：车辆调度；现代物流；联合配送；调度算法

DOIDOI：10.11907/rjdk.162229

中图分类号：TP319

文献标识码：A文章编号：1672-7800（2016）012-0107-02

0 引言

现代物流业着眼于供应链体系发展，带动新型工业化、农业产业化和流通现代化，逐渐成为国民经济的基础产业。各种物流信息应用技术如GPS、北斗导航等技术已广泛应用于各种物流活动过程。同时，随着物联网技术和电子商务的快速发展，传统单一的物流模式逐渐被联合配送、动态配送和大规模跨区域配送取代，传统单一的车辆调度模式已经难以支持现代物流业配送需求。

现实物流调度中需求各异，涉及的车辆调度因素众多，甚至相互冲突，在客户满意度和调度成本上需要相互平衡，特别是随着大数据计算、物联网技术、智能通讯以及电子商务评价模式的出现，车辆调度需要综合考虑车辆、客户、货源、路况、用户评价等各种因素[1-2]。

鉴于此，本文从系统工程角度分析资源、车辆、客户需求，对跨区域配送中关键要素进行分析，研究构建基于联合配送的调度模式，构建面向多方用户需求的需求池和调度池，对面向不同约束的调度需求以及联合配送车辆调度进行建模并设计相关算法，以实现在多约束条件下的最优调度算法。

1 研究现状

1959年由Dantzig和Ramser首次提出[3]的调度问题来自于公路交通运输管理。随着电子商务和信息技术的发展，传统大批量、少批次的物流模式已经不能适应复杂多变的调度需求，小批量、多批次、客户需求的动态性使得配送区域更加模糊，区域间交叉配送和联合配送现象日趋频繁[4]。Hariklis和Powell[5]首次提出开放式车辆调度问题，Arantilis[6]对鲜肉配送的车辆调度问题进行了研究；有学者采用混合遗传算法和禁忌算法对开放式车辆调度问题模型进行求解，提出了开放式车辆调度问题最优解的检验方式；李延晖等研究了沿途多点的开放式车辆调度问题，并设计带有补货控制因子的蚁群算法进行求解[7，8]。上述文献主要是对需求稳定的开放式车辆调度问题展开研究，但对优化目标选择、多配送中心、车辆共享管理等核心问题没有详细分析。因此，本文针对国内物流配送现状，从节约成本角度出发，提出将配送资源、客户转化为资源池概念，通过充分联合，转化为联合配送的车辆调度问题。

2 联合配送调度算法

2.1 联合配送含义

联合配送指共同配送、协同配送。在一个规模化的区域内存在多个配送中心、多批次的货物资源，为了降低物流成本，打破单个车辆物流调度的局限性，多公司合作实现大范围的合理化配送，通过集中配送来提高物流使用效率，进而提高配送车辆利用率，达到共享物力资源和车辆资源效果。联合配送还存在分区配送和跨区域配送，区别在于配送中心是否联合响应。

以PN代表配送中心，UN代表用户需求，分区配送策略建立“1-N”模式，一个配送中心负责所在区域内的所有用户需求，各配送出于利益关系互不关联，调度车辆负责所在区域的用户需求，区域配送模式如图1所示。在联合配送模式中，不同配送中心可根据用户需求相互调度车辆，实现跨区域内车辆、资源协同和共享，配送中心可从整个区域范围内考虑车辆调度问题，解决了物流能力不平衡问题，满足了小批量、多批次的物流需求，节约了成本，这种模式使得更大规模的区域配送调度成为可能。联合配送模式如图2所示。

2.2 联合配送业务需求分析

联合配送过程中需要综合考虑多项业务需求因素，这些因素包括配送中心基础信息、车辆信息、货物信息、位置信息等，由此产生几大功能需求，包括车辆管理、货物管理、调度管理、地图可视化、基础数据管理等功能。因此，物流调度系统必须根据业务需求制定科学合理的功能需求，利用调度算法进行快速优化，产生实时调度计划，以提高联合物流调度系统效率和效益。联合配送算法必须将问题进行分解及简化，并抽象出相应的数学模型，再通过各种优化算法运算出最优解。算法首先需要根据初始化资源状态统计出车辆到货物的最短距离，通过区域优化算法，计算出为每个客户提供配送服务所属的配送区域；然后系统将客户需求整合以确定各配送中心要服务的客户。因此，联合配送调度问题分解为各个独立的单区域配送问题。分解后的各个独立问题可以综合运用遗传算法求解，最终求出最优解和车辆配送路线。

2.3 联合配送算法设计

车辆调度算法中最早的遗传算法由Holland提出，其核心思想是在任意一个群中优秀个体都会出现指数增长的方向，其中优化对象可以是连续型的，使用随机选择策略经过交叉繁殖和变异等遗传行为，直至算法实现收敛。联合调度算法需要预估车辆的配送条件，资源约束条件包括货物资源、车辆资源、需求资源等，车辆调度中的资源约束条件越多，车辆调度线路的安排就越复杂，每台车辆在资源约束下的任务量就越小，同时车辆跨区域调度越频繁，配送中心整体成本就越低。

为了实现车辆调度最优化，根据配送网络中客户的需求量建立资源池，预先估计完成调度所需要的车辆数为m，建立模型如下：

其中Qmaxr表示区域范围内可调度车辆最大需求量，Qmaxr表示区域范围内车辆最小需求量，0<<1表示资源约束条件，资源需求越多约束条件越多。联合配送信息发生在配送计划的执行过程中，算法设计“资源池建立+区域配送阶段+联合配送阶段”的三阶段求解策略，对联合配送模型进行求解，算法设计思想如下：

第一阶段：根据现有配送中心基础信息、车辆信息、货物信息、位置信息等建立调度资源池，并生成现有静态状态；第二阶段：根据已知需求信息制定初始优化阶段的调度计划。该阶段利用遗传算法进行全局优化，产生初始调度计划；第三阶段：根据需求信息变化情况优化。该阶段将在执行第二阶段制定的配送计划过程中，通过需求信息变化更新资源池。在资源池变动情况下分析新需求，利用遗传算法快速优化，产生实时调度计划。具体流程如图3所示。

3 结语

联合车辆调度及路线的优化决策涉及众多因素，比如配送中心位置、客户分布及需求、成本因素、时间因素等。本文针对跨区域多配送中心联合配送车辆调度问题展开研究，分析了现阶段联合配送调度算法现状，对现有遗传算法进行了改进，建立了“资源池建立+区域配送阶段+联合配送阶段”的三阶段求解方案，以实现车辆调度优化策略，实现物流调度的实时化、高效化和智能化，为物流工作人员优化车辆调度业务提供技术支持。

参考文献：

[1] 刘云忠，宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报，2005，19（1）：124-130.

[2] 张景玲，赵燕伟.多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统，2010，16（3）：543-550.

[3] DANTZIG G B， RAMSER J H. The truck dispatching problem[J]. Management Science，1959，4（6）：80-91.

[4] 葛显龙.面向云配送模式的车辆调度问题及算法研究[D].重庆：重庆大学，2011.

[5] LI SARIKLIS D， POWELL S. A heuristic method for the open vehicle routing problem[J]. Journal ofthe Operational Research Society，2000，51（5）：564-573.

[6] TARANTILIS C D， KIRANOUDIS C T. Distribution of fresh meat[J]. Journal of Food Engineering，2002，51（1）：85-91.

[7] 陶胤强，牛惠民.带时间窗的多车型多费用车辆路径问题的模型和算法[J].交通运输系统工程与信息，2008，8（1）：113-117.

[8] 霍佳震，王新.基于约束规划求解车辆调度问题[J].物流技术，2005（9）：110-112.

[9] 施朝春，王旭，葛显龙.带有时间窗的多配送中心车辆调度问题研究[J].计算机工程与应用，2009，45（34）：21-24.

（责任编辑：杜能钢）