内容发布更新时间 : 2025/10/3 17:58:44星期一 下面是文章的全部内容请认真阅读。
带中转点的联盟运输调度的遗传算法研究 蔡延光，李永生，林灼强，丁志勇 （广东工业大学 自动化学院 ）
摘要：结合城市货物运输的具体特点，分析了多供应点、多中转点的联盟运输调度问题的优越性。在分析联盟运输调度特点的基础上，建立了优化确定联盟运输调度问题中转点的数学模型，并构造了求解该问题的有效的遗传算法，算法中针对具体问题的特点，采用较新的交叉算子。实例计算表明：本文提出的模型和算法能够有效的解决AVRP中转点的确定问题。 关键字：联盟运输调度；中转点；优化；遗传算法
Research of Genetic Algorithm on Allied Vehicle Routing Problems with Transfer Stations
CAI Yan-guang, LI Yong-sheng, LIN Zhuo-qiang ，DING Zhi-yong
(Faculty of Automation, Guangdong University of Technology, Guangzhou 510090, China)
Abstract：Considering the characteristics of urban freight transportation，the advantage and the characteristics of the Allied Vehicle Routing Problem(AVRP)with transfer stations is analyzed，on the basis of which an optimized mathematical model to solve the problem is established and the effective genetic algorithm for the model is constructed。In this algorithm，the new crossover operator is designed。Numerical calculation results indicate that the proposal model and algorithm effectively solve the Allied Vehicle Routing Problem(AVRP)with transfer stations。
Keyword： Allied vehicle routing problem；transfer station；optimization；genetic algorithm 1 引言
货物运输车流是城市交通流的重要组成部分，它在满足社会需求的同时也给城市的交通带来了拥挤问题，为了减少部分运输路段载荷、缓解交通拥挤和促进城市交通设施的均衡使用，在城市中心区与外部区之间优化选择一定数目的位置，设置具有一定作业能力的货物中转点，以迫使由城市外部区去往中心区的货物运输需求分流为两个以上的运输路径进行运送，从而减轻城市内一些路段的车流载荷，在一定程度上缓解了城市交通拥挤现状。但是，在运输计划编制时不能简单的指定某个中转点为某些固定的客户服务。因此如何在运输费用最省的前提下合理为每一次运输合理选择中转点就成为带中转运输调度问题的一个关键。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自然适应全局优化概率搜索算法。与传统的优化算法相比具有运算简单、搜索过程灵活、搜索效率高以及隐含并行性等特点，是一类可用于复杂系统优化计算的鲁棒搜索算法。本研究针对带中转运输调度问题的特点，构造了优化确定中转点的遗传算法，并通过实验计算分析了该算法的有效性。 2 问题的描述及数学模型的建立
联盟运输调度问题[1]（Allied Vehicle Routing and Scheduling Problem，AVRP&AVSP）是指在满足运输要求的前提下，快速组织多种交通工具，允许车辆中转，设计物流运输工具
组合、时间组合、线路组合等最优策略，并为每一次运输设计最优的行车线路和时间表，追求经济效益的最大化和实现过程的最优化。
基金项目：国家自然科学基金资助项目（60374062）；广东省自然科学基金资助项目（04009488）；广东省科技计划项目（2005B10101015）。
作者简介：蔡延光 ,博士，教授，主要研究方向为组合优化、人工智能、决策支持系统 ；李永生,硕士研究生，主要研究方向为系统优化与控制。 E-mail : lynne5101 @163.com 。Mobile :13433981140
与普通的运输调度问题（Vehicle Routing Problems，VRP）相比，AVRP具有三个显著的扩展特征：允许使用不同类型交通工具、允许使用多层次交通网络、允许使用货物中转设施。近三十年来，VRP是组合优化的研究热点之一，但对AVRP研究很少。
本文针对允许使用不同类型车辆、允许中转、允许使用多层次交通网络的AVRP，在建立选取最优中转点的数学模型的基础上，用改进的遗传算法进行求解。针对涉及的问题进行如下说明[2]：
(1) 中心区：即城市中集土地混合使用、行政、文化、商业、旅游以及市民居住于一体，具有人口密度高、商业发达、行政化水平高、文化活动频繁以及路网密度高、车流流量大等特征的区域。
(2) 外部区：即远离或邻近城市并与城市产生往返货流的地点、港口、火车站、航空站、工厂、仓库等邻近城市的生产与保管设施(城市内除外)以及城市入口与出口。 (3) 供应点：位于城市的外部区，集存储、集货、分拣等功能为一体的配送中心。 (4) 中转点：位于城市中心区与外部区之间，具有一定作业能力的基础设施。 对带中转点的联盟运输调度问题进行研究可以从两个方面考虑：
(1) 将带中转点的运输调度问题分成两个阶段：第一阶段根据某市中心区各需求点的分布情况，合理选定运输中转点。货物可以以适当的提前期运达中转点；第二阶段是在优化选定中转点之后，综合考虑各种配送要素，结合联盟企业共同配送等策略进一步优化配送方案。实现货物有中转点到最终客户的优化配送。
(2) 将带中转点的运输调度问题本身看作一个复杂的组合优化问题进行研究，这种方法的研究重点集中在如何合理的缩小搜索空间和简化求解步骤上。本文选取第一类方法对带中转点运输调度问题进行研究，集中讨论第一阶段的调度问题。第二阶段的调度问题另文讨论。 带中转点的运输调度问题满足如下特点和要求：①中转点的数目已知且能够随时提供所需的中转服务。②外部区与中转点之间的货物运输车辆为单一大卡车类型，即使用量最多的车型；③考虑多个供应点经一定数量中转点为需求点配送．④中转点内小货车作业能力不受限制，即中转点能够满足卡车货物换装要求。⑤每个需求点的配送服务仅经过一个中转点。AVRP的网络模型描述如下[3,4]：
设 是一个边赋权的连通网络， 是顶点集即需求点的个数（共 个）， 为（无向）边集。定义 为 个可供选择的中转点的个数； 为各需求点的易达程度系数。 与到达各需求点的道路情况和是否有交通限制等要素有关， =1表示到达该中转点不受任何限制， =0表示到达该中转点受到无法到达的限制；问题的研究即为各需求点选取合理的中转服务点，从而分别将 个需求点所需求的货物分成不同的组合运达选定的中转点。然后经过合理换装配送到各个需
求点。该问题的优化求解的数学模型如下： Min + + (1) s.t.
各式中 表示式供应点的集合， 表示中转点的集合， 表示需求点的集合； 表示从第 个供应点到第 个中转点的单位运输费用， 表示从第 个供应点到第 个中转点的货物运输量； 表示第 个供应点到第 个中转点的中转费用； 表示第 个中转点到第 个需求点的单位运输费用。 第 个中转点到第 个需求点的货物运输量。(1)式中各部分顺序表示为将货物运达选定中转点的费用、选定中转点的中转费用、由中转点到达需求点的运输总费用，在中转点到需求点的过程中考虑了各需求点的易达程度。式(2)表示选择的中转点不超过备选中转点的个数 ；式(3)保证每个需求点只能由一个中转点提供服务。式(4)表示各个需求点的需求数量不能超过中转点的容量M；式(5)表示式供应点必须向选中的中转点分配货物。式(6)表示第 个中转点是否被选中；式(7)表示第 个需求点是否有服务需求。 3 问题的遗传算法
从建立的数学模型可知，确定中转点就是一个优化的问题，遗传算法在解决优化问题方面具有一定的优势。特别是在求解TSP问题中取得了一定的成果。在此我们可以借鉴，构造遗传算法如下： 3.1 染色体的结构
为了提高搜索效率和表达的方便，采用自然数编码[5]。可供选择中转点的个数为 ，从 个中转点中可重复随机的选取 个分别分配给 个需求点作为一个初始解，则群体的个体数目则为 ，X 表示第 t代的第 个个体， 。在求解的运输调度问题中则表示为按需求点编号顺序排列的中转点组合，是一种可能的中转点分配方案。染色体中允许有相同的基因位，在求解的运输调度问题中则表示多个需求点的货物可以允许在一个中转点进行中转作业。例如，城市的外部区和中心区之间有3个中转点可供选择，城市中心区6个需求点并顺序编号，则位串{2 3 2 3 1 2}表示第1个需求点在第2个中转点中转换装，第2个需求点在第3个中转点中转换装，依次类推。 3.2 产生初始种群
初始种群(chrom)由种群规模决定的若干染色体构成。种群中的任一染色体必须遵循染色体的结构要求。最终形成的染色体可由一个二维矩阵表示。 3.3 适应度函数
本问题中适应度的计算按照个体目标值ObjV由小到大的顺序进行排列，并返回一个包含对应个体适应度值FitnV的列向量。 3.4 自然选择
这里采用轮盘赌选择法，并在轮盘赌选则法的基础上采用了最佳个体保存选择策略，就是用适应度值最大的染色体代替下一代适应度最低的染色体。这样可以保证最优个体可 以生存到下一代，避免了最优个体的中途丢失，并且加速算法向最优解收敛。 3.5 染色体的交叉
带中转点的运输调度问题具有组间无序、组内无序的特性，如果单纯的使用一般的交叉算子往往会使一些优秀的子串被破坏，并且在两父个体相同时，无法再产生新的个体。在此采用