摘要：结合城市货物运输的具体特点，分析了多供应点、多中转点的联盟运输调度问题的优越性。在分析联盟运输调度特点的基础上，建立了优化确定联盟运输调度问题中转点的数学模型，并构造了求解该问题的有效的遗传算法，算法中针对具体问题的特点，采用较新的交叉算子。实例计算表明：本文提出的模型和算法能够有效的解决AVRP中转点的确定问题。

关键字：联盟运输调度；中转点；优化；遗传算法

1        引言

货物运输车流是城市交通流的重要组成部分，它在满足社会需求的同时也给城市的交通带来了拥挤问题，为了减少部分运输路段载荷、缓解交通拥挤和促进城市交通设施的均衡使用，在城市中心区与外部区之间优化选择一定数目的位置，设置具有一定作业能力的货物中转点，以迫使由城市外部区去往中心区的货物运输需求分流为两个以上的运输路径进行运送，从而减轻城市内一些路段的车流载荷，在一定程度上缓解了城市交通拥挤现状。但是，在运输计划编制时不能简单的指定某个中转点为某些固定的客户服务。因此如何在运输费用最省的前提下合理为每一次运输合理选择中转点就成为带中转运输调度问题的一个关键。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自然适应全局优化概率搜索算法。与传统的优化算法相比具有运算简单、搜索过程灵活、搜索效率高以及隐含并行性等特点，是一类可用于复杂系统优化计算的鲁棒搜索算法。本研究针对带中转运输调度问题的特点，构造了优化确定中转点的遗传算法，并通过实验计算分析了该算法的有效性。

2  问题的描述及数学模型的建立

联盟运输调度问题^[1]（Allied Vehicle Routing and Scheduling Problem，AVRP&AVSP）是指在满足运输要求的前提下，快速组织多种交通工具，允许车辆中转，设计物流运输工具组合、时间组合、线路组合等最优策略，并为每一次运输设计最优的行车线路和时间表，追求经济效益的最大化和实现过程的最优化。 

与普通的运输调度问题（Vehicle Routing Problems，VRP）相比，AVRP具有三个显著的扩展特征：允许使用不同类型交通工具、允许使用多层次交通网络、允许使用货物中转设施。近三十年来，VRP是组合优化的研究热点之一，但对AVRP研究很少。

本文针对允许使用不同类型车辆、允许中转、允许使用多层次交通网络的AVRP，在建立选取最优中转点的数学模型的基础上，用改进的遗传算法进行求解。针对涉及的问题进行如下说明^[2]：

(1) 中心区：即城市中集土地混合使用、行政、文化、商业、旅游以及市民居住于一体，具有人口密度高、商业发达、行政化水平高、文化活动频繁以及路网密度高、车流流量大等特征的区域。

(2) 外部区：即远离或邻近城市并与城市产生往返货流的地点、港口、火车站、航空站、工厂、仓库等邻近城市的生产与保管设施(城市内除外)以及城市入口与出口。

(3) 供应点：位于城市的外部区，集存储、集货、分拣等功能为一体的配送中心。

(4) 中转点：位于城市中心区与外部区之间，具有一定作业能力的基础设施。