多时段可搭载零担物流路径优化问题模型及算法研究

       文章编号：1007-5429(2019)06-0064-07

       DOI：10.19495/j.cnki.1007-5429.2019.06.008

       1 引言

       随着物流业对我国经济的影响加剧，物流行业的发展越发得到相关部门的重视。而公路运输是国内货物运输的主要方式之一，据统计，2017年公路运输的整体市场规模达到了5万亿，公路货运量占全部货运量的78.0％，其中公路零担物流运输规模为1.54万亿，占比30.8％。零担物流一方面受益于宏观经济稳定增长，另一方面受益于消费升级下的电子商务发展，并且其服务对象面广、服务产业多、受产业生命周期影响小，所以零担物流业务呈现快速发展的趋势。此外，在零担物流中承运人车辆运输服务可分为任务可搭载和不可搭载两种情况，相比任务不可搭载而言，任务可搭载可使承运人节约49％的运输成本[1]。

       目前，针对可搭载的零担物流路径规划问题的研究取得了一定的成果。Mesa-Arango R等人[1]在任务可搭载的基础上，将m-PDVRP模型应用在零担物流路径优化中，并采用分支定价算法对模型求解；高超锋等人[2]建立以轴辐式网络总成本最小化为目标的混合整数线性规划模型，并在考虑枢纽中心建造成本的基础上提出改进的最大最小后悔值的不确定性决策方法，优化车辆配送路线从而减少零担物流网络总成本；王雁凤等人[3]针对大规模零担物流路径优化问题展开研究，建立了基于双层规划的轴辐式模型，并采用遗传算法求解模型；ZENER等人[4]认为零担物流运输路径规划由三部分构成：①从起点到枢纽站；②枢纽站之间的转运；③从枢纽站到终点，并开发了一个综合框架同时解决这些问题。Barcos L等人[5]以整合每对始发地—目的地的物流量为切入点，采用基于蚁群算法的优化方法优化承运人的运输路线，最大限度地降低总成本。

       然而，考虑多时段的零担物流可搭载问题的研究相对不足，Yan等人[6]在考虑多时段的基础上，建立了零担物流随机规划模型并提出了改进的粒子群算法对模型求解。而考虑多时段的特征后，问题的求解难度进一步增加，采用上述研究所提出的智能算法将使得计算时间显著增长。因此，本文考虑在多时段任务可搭载的情况下，从承运人的角度出发，建立相应的数学模型，提出一种基于动态规划的启发式(a heuristic algorithm based on dynamic planning，HAbDP)算法进行求解，并通过两个不同规模的算例对模型和HAbDP算法的有效性进行分析。

       2 问题描述及建模

       2.1 问题描述

       假设在可达区域内有V个节点且节点间的距离已知，在第t天承运人共有N[，t]个托运任务需要完成，且每个任务的起止点、物流量和运输费用等信息已知，在任务可搭载的基础上，综合考虑承运人的车辆载重和运输距离等约束，通过合理规划车辆行驶路线使其收益最大成为一个关键问题。

       2.2 模型假设

       (1)假定不同托运人的货物可以混装，且不可分割；

       (2)节点间的距离已知；

       (3)每个托运任务信息已知；

       (4)油耗与车辆的负载率成线性相关[7]。

       2.3 参数定义及数学模型

       G为有向图，G=(V，E)；V为全部节点的集合；E为弧的集合，E=｛(i，j)i，j∈V｝；N[，t]为第t天承运人承运的托运任务集合；T为计划期；d[，ij]为弧(i，j)的长度；x[t][，ij]为二进制变量，如果承运人第t天从节点i出发直接到节点j，x[t][，ij]=1，否则x[t][，ij]=0；l[ijkt][，rm]为二进制变量，如果第t天承运人承运的从节点r到节点m第k个任务经过弧(i，j)，则l[ijkt][，rm]=1，否则l[ijkt][，rm]=0；q[kt][，rm]为第t天从节点r到节点m第k个任务的运量；p[kt][，rm]为q[kt][，rm]的报价；g[t][，ij]为第t天承运人经过弧(i，j)时，车辆的物流量；h[t][，ij]为第t天承运人经过弧(i，j)时，车辆的负载率；D为车辆的最大行驶距离；Q为承运人车辆的最大载重；e[，1]为车辆空载时行驶单位距离的油耗成本；e[，2]为车辆满载时行驶单位距离的油耗成本；e[t][，ij]为第t天承运人车辆经过弧(i，j)时单位油耗成本。

       目标函数：

       Maxz=p[kt][，ij]-d[，ij]x[t][，ij][h[t][，ij](e[，2]-e[，1])+e[，1]]

       (1)