本文是一篇物流管理论文，本文建立了基于禁忌搜索的两阶段算法框架，并在此框架下进行了相应的对比实验。总的来说，本文的主要研究成果与创新点如下：（1）以标准 TTRP 问题为研究对象，做出合理假设并建立甩挂运输路径规划的相关模型，以此为基础建立基于禁忌搜索的两阶段启发式算法。算法的第一阶段包括初始路径的分配和生成，得到第二阶段禁忌搜索的输入初始解。每个阶段均引入不同的邻域算子，来优化过程解。
第 1 章 绪论
1.1 研究背景及意义
1.1.1 研究背景
中国物流市场规模在 2013 年首次超越美国，位列世界第一。2018 年，全国社会物流总额 283.1万亿元，社会物流总费用 13.3万亿元，社会物流总费用与 GDP的比率为 14.8%。其中，运输费用 6.9 万亿元，运输费用与 GDP 的比率为 7.7%。而同期美国社会物流总额占 GDP 比重仅为 8.5%。与此同时，2018 年，公路运输完成货运量 395.9 亿吨，且公路货运量占社会货运周转总量的比例已经达到 78.22%。公路运输已经成为国内货物运输的主要运输形式。
表 1-1 2008-2018 年国内物流总额及增长速度
公路货物运输是一个国家综合运输体系的重要组成部分，对经济和社会发展具有重要战略意义，随着我国公路货物运输的占比持续增长，其在社会整体运输系统中的地位也日益突出。而伴随着经济快速增长，也带来了诸如全球变暖，空气污染等环境和气候问题，促使交通运输业向更高层次发展，降低物流成本，变得更环保节能，更高效便捷。同时，随着移动互联网和电子商务的发展，巨大的消费需求对国内的物流配送和快递收发在时效性和高效性上也提出了更高的要求。
.............................
1.2国内外相关研究现状
TTRP 问题是 VRP 问题的衍生问题，在求解时，考虑到求解规模和求解质量等因素，现有的研究大部分采用元启发式算法。在使用元启发式算法解决问题的过程中会使用到不同的移动策略。由于本文的研究重点为移动策略，所以在总结国内外学者的相关研究时，会将注意力主要集中在算法的选择，移动策略的设计原则及算子的选用等方面。同时由于 TTRP 问题领域相关针对性研究的有限，本文在第二部分总结了 VRP 问题的其他衍生问题的相关研究。
1.2.1TTRP 问题整体研究概况
（1）标准 TTRP 问题
标准 TTRP 问题最初由 Chao[1]在 2002 年提出，抽象出两种客户类型，两种车辆类型以及三种路径类型，将总体路径长度最短作为最终的求解目标。同时 Chao 构造了 21 个通用的 TTRP 测试算例，使用了禁忌搜索算法来求解该问题。Scheuerer[2]，Lin[3]等人基于 Chao 提出的标准 TTRP 问题，进行了更深入的研究。Scheuerer 同样使用禁忌搜索算法来求解标准 TTRP问题，但在构建阶段，Scheuerer提出了新的 T-Sweep 算法，提升了该阶段的构造结果，对算法的求解性能进行了一定程度的提高。Lin[3]则首次使用了模拟退火算法（Simulated Annealing, SA）来求解标准 TTRP 问题。
（2）带时间窗的 TTRP 问题
由于甩挂运输中卡车和挂车可以分离和重新挂载，所以在时间窗约束上会与一般的路径规划问题有所区别。Drexl[4]等人研究了甩挂运输车辆路径规划问题及其转运问题，同时对时间窗、空间、运载量等多个同步约束条件下的甩挂运输问题进行了研究。Lin[5]等人对 Chao 提出的标准 TTRP 问题增加了时间窗的约束，设计了相应的模拟退火算法进行求解。Parragh[6]等人在求解带时间窗的 TTRP 时使用了分支定价算法和大规模邻域搜索算法，同时还设计了相应的定价规则以及替代下限的计算方法。
.............................
第 2 章 甩挂运输现状及算法
2.1 甩挂运输概述
2.1.1 甩挂运输简介
一般来说，甩挂运输（Truck and Trailer Transportation）是指利用牵引车拖带挂车，将货物运送至目的地，而挂车可以在卸挂点进行卸挂或重挂作业，从而实现连续作业的一种运输模式。通过牵引车或者卡车与挂车的分离、挂载等作业，甩挂运输完成了运输方式上的资源配置优化。在公路运输部分，带挂牵引车在允许的地点甩下一个或多个挂车，或者牵引车直接到达目的地点，从而挂上一个或多个挂车继续作业，实现灵活准确的运输服务。应用到多式联运时，公路运输部分的甩挂运输行驶至铁路或水路联运场站，进行卸挂作业，卸下的挂车由平板列车或者货运船，经过铁路与水路等大容量干线运送至目的地的联运场站，再由该区域的甩挂车挂载，继而运送至货物需求地，形成完整的多式联运过程。相比于普通公路运输，甩挂运输与多式联运的配合，可以有效利用不同运输方式的优势，提高综合运输系统的资源配置效率和物流服务质量。
图 2-1 甩挂分离及结合示意图
..........................
2.2 甩挂运输发展现状
欧美等发达国家和地区在上世纪四十年代开始了甩挂运输的发展，并且在规模较大的货运公司被大比例采用。甩挂运输的优势受规模经济影响较大，即货物的运输量和运输频次对其影响较大，最近几年，发达国家的大型货运公司甩挂运输的采用率接近 100%，利用卡车拖带挂车组成的完备车辆运输承担的运输量占总货运量的七八成，挂车与牵引用的卡车数量比达到了 1 比 2.5。
甩挂运输的概念进入我国是在上世纪九十年代，1996 年，政府出台了《关于开展集装箱牵引车甩挂运输的通知》，开始在全国各地扶持运输企业对甩挂运输的引进。十三年后，2009 年，国务院刊发了《关于实施成品油价格和税费改革的通知》，常年阻碍汽车货物运输中的规费征收被进一步合理化。同年 12 月，包括交通运输部的五个国家相关部门出台了《关于促进甩挂运输发展的通知》，旨在通过政策倾斜，加大对于甩挂运输场站建设的扶持力度，按照行业的作业和实施特征，充分学习海外经验，对已有的场站进行合理的升级改造，从而建成层次分明、功能完善、各环节连接顺畅的甩挂运输场站体系，作为甩挂运输发展的基础。除此之外，2010 年交通运输部从国内的十个省市开始试点运行甩挂运输，进一步地，《道路甩挂运输标准化导则》、《甩挂运输车辆技术要求》、《厢式挂车技术条件》、《货运挂车系列型谱》等文件的出台，促进了甩挂运输进入实质发展的阶段。
国家在政策层面的大力支持反映了对甩挂运输发展的重视，而从实际的推进来看，上海、深圳、山东、厦门、宁波等沿海城市的集装箱港区联动疏运，广州、佛山、重庆、湖南等地的大型工业企业中间品的流转，广东、周口、大连等城市建成的为解决区域物流配送需求的城际快运网络都使用了甩挂运输作为主要的运输方式。早期的甩挂运输大豆应用在港口集装箱运输作业当中，而目前甩挂运输的应用场景已扩展至公路货物运输。
................................
第 3 章 问题描述及数学模型 ........................ 20
3.1 TTRP 问题描述 ..................................... 20
3.2 问题分析 ........................................... 22
第 4 章 算法设计与研究 ..................................... 28
4.1 算法框架 .................................. 28
4.2 算法流程 ................................... 30
第 5 章 计算实验及分析 ..................................... 47
5.1 数据来源与说明 ......................................... 47
5.2 计算环境 ................................ 48
第 5 章 计算实验及分析
5.1组别设置
为了研究不同的移动策略对于求解质量的影响，本文试图回答三个问题：
（1）是否存在贡献度最大的算子；
（2）是否存在优于其他所有策略的算子组合；
（3）是否存在最优的算子数目或者说较好的算子数目。
为此，本文设计了如下表所示的策略组合ℋ , ，其中λ = 1, … ,8表示邻域算子的数目，而 l 表示该组合的序号。
表 5-2 实验组别
.............................
第 6 章 总结与展望
6.1 研究总结
甩挂运输作为欧美发达国家及地区的主要公路货运运输方式，势必也将成为中国未来公路运输中占比重要的运输方式。优化运输方式以及运输线路，无论是在经济层面还是社会层面都会带来积极的影响，对于国内物流行业的产业升级也是具有重要意义的举措。优化车辆路径更是重中之重，然而目前国内外关于甩挂运输路径优化的研究，主要集中于 TTRP 问题求解算法的性能提升上，并未对算法中移动策略的选用规则做出足够充分的说明，为了探究 TTRP 问题求解时，移动策略与求解结果之间的相关关系，本文建立了基于禁忌搜索的两阶段算法框架，并在此框架下进行了相应的对比实验。总的来说，本文的主要研究成果与创新点如下：
（1）以标准 TTRP 问题为研究对象，做出合理假设并建立甩挂运输路径规划的相关模型，以此为基础建立基于禁忌搜索的两阶段启发式算法。算法的第一阶段包括初始路径的分配和生成，得到第二阶段禁忌搜索的输入初始解。每个阶段均引入不同的邻域算子，来优化过程解。
（2）
