摘要：联盟运输调度问题（AVRP）是在基本运输调度问题（VRP）基础上衍生出来的复杂组合优化问题，是近年来物流控制优化中的研究热点。建立了一类实用性强的联盟运输调度问题模型，从选择策略和信息素挥发速度两方面简要改进了基本蚁群算法，较好的克服了其最优解不稳定和易陷入局部最优等缺点；

其次，依据AVRP模型的特点，从构造三类分支回路和处理遗漏客户点入手构造了AVRP的可行解，解决了用蚁群算法求解时不易发现可行解的问题；最后用改进的蚁群算法对AVRP进行了求解，实验分析表明可以较好得解决现实中常见物流运输调度问题。

关键词：运输调度；联盟运输调度；蚁群算法；物流

1 引言[1]

物流成本占GDP比重是衡量一个国家物流水平高低的重要标准。发达国家物流成本占GDP比重为10%左右，而目前我国此比例为16.7%，足以见证物流成本之高昂。在国际物流新思想以及复杂竞争环境的影响下，我国正日益重视物流科技的发展和应用，从而降低物流成本，并为企业和社会带来可观的经济效益。其中，将提高物流运输调度水平作为重点之一。

运输调度问题（Vehicle Routing Problems，VRP）即组合优化中的车辆路径问题，自1959年提出以来，时至今日，已经取得了巨大的理论发展，模型一再扩充，算法层出不穷，某些理论已经产生了实际的经济效益。然而在随着我国物流企业或按地域或按行业或按行政归属等组成物流联盟，某个物流企业单兵作战的方式已不再适用，一种基于物流联盟的运输调度模型亟待产生。

    联盟运输调度问题（Allied Vehicle Routing Problems，AVRP），即基于物流联盟的运输调度最优化，就是在满足运输要求的前提下，在联盟内快速组织多种交通工具，允许车辆中转，设计物流运输工具组合、时间组合、线路组合等最优策略，并为每一次运输设计最优的行车线路和时间表，追求经济效益的最大化和实现过程的最优化。AVRP是强NP难的问题，带物流联盟特征的AVRP在国内外研究很少，然而对各类VRP研究却较为丰富^[1,2,3,4]。本文拟用改进蚁群算法求解一类模型相对简单的AVRP。

2 AVRP模型的建立

首先引用智能运输调度系统模型结构分类库^[5]对AVRP结构进行具体描述：

车队结构参数：一个车队，固定位置，一辆车或一辆以上，车辆载重量不完全相等；

供应结构参数：一个供应点，位置确定；

需求结构参数：输送型，全部满足需求点的需求；

网络结构参数：无向，边弧权值固定且无任何关系，多重图拓扑结构；

作业类型参数：允许混装，车辆完成任务后返回出发点；

约束条件：软时间窗，距离限制；

目标函数条件： 总运输费用最小。