1. 研究目的与意义（文献综述）

我国电商发展较快，尤其“B TO C”购物模式极大的影响了人们生活。快递行业作为与电商业有着密切相关的行业，借势飞速成长，备受瞩目。但物流“高成本，低时效”的瘤疾制约了电商业的发展。快递行业在我国属于劳动密集型行业，技术含量相对较低。缺乏先进的生产管理手段，是造成“高成本，低时效”的主要原因。其中最后一公里配送是整个电商物流过程中重要的一环^[1]。电商的蓬勃发展使得目前很大一部分的物流包裹均来源于线上电商订单。在中国，该比例超过了60%。这些包裹在配送的最后环节，是由快递员将包裹从网点送到消费者手中。另一方面，随着互联网逐渐向线下渗透，涌现出了越来越多的同城包裹配送需求，如外卖订单或鲜花蛋糕等等同城订单。这两类包裹的配送是目前中国最后一公里配送中最典型的场景。

具有时间窗约束的取送货问题 ( pickup anddeliveryproblem with time windows， PDPTW) 是一类特 殊 的 具 有 时 间 窗 的 车 辆 路 径 规 划 问 题( VRPTW) ． 在 PDPTW 问题中，车辆被安排前往不同的地点取货并将货物送往相应目的地，车辆到达每个取货点或目的地的时间均有约束．其中，PDPTW 的 相 关 文 献 最 早 可 追 溯 到 1980 年，Psarafis^[2]采用动态规划的方法求解了需求少于 10 个的算例． 随后出现的精确算法包括分支定价法和分支剪切法． 而更多文献专注于设计启发式算法以增大可求解的 PDPTW 规模． Nanry 等^[3]最早采用了禁忌搜索算法进行求解，并创建了一组基准算例来检测算法的效果，每个算例最多包含 50 个需求． 此后 Li等^[4]提出了一种整合模拟退火和禁忌搜索的算法，并进一步扩大了算例的规模至 100 个需求． Lau等^[5]提出了禁忌搜索算法中几种构建路径的方法． Bent等^[6]采用了两阶段混合算法，第一阶段用模拟退火算法减少车辆数， 第二阶段用大邻域搜索算法最小化路径长度。Ropke等^[7]在此基础上提出了自适应大邻域搜索算法．目前国内对 PDPTW 的研究有限，最近的结果主要为潘立军等^[8]提出的一类时差插入法，以及以该插入法为基础的遗传算法，程谦等^[9]引入匹配度的概念以及时差插入法，提升算法的运算效率。 国外最近的研究进展主要集中于具有特殊结构的 PDPTW． 例如需求可拆分的PDPTW^[10]和具有后进先出的装载约束的 PDPTW^[11].同时我们可以注意到，国内外研究的问题规模相对较小，问题中客户量少于100，对于大规模问题缺乏研究^[12]。此外，对于取送货的先后问题，一般被认为是同时或者忽略掉了，而在目前同城快递行业中，先取后送这一情况鲜被研究。

基于以上，本文将着力采用元启发式算法，探索领域搜索，禁忌搜索和模拟退火等等的结合，产生一种改进的算法，具有高效的领域搜索和全局搜索的能力，通过在较大规模Benchmark上实验，试图提高解决先取后送约束下的PDPTW的效率，这将有利于推动同城快递服务中最后一公里的研究。

2. 研究的基本内容与方案

2.1设计的基本内容和目标

基本内容：最后一公里物流核心问题是(vehicle routing problem)车辆路径问题，是一种经典的带多种约束的组合优化问题。由于实际问题规模普遍较大及其是np-hard问题的特性，元启发式的优化方法成为主流方法。本文主要研究带有时间窗口，及先取后送约束的车辆路径问题(pdptw)，采用邻域搜索和模拟退火、禁忌搜索等相结合方法，在较大规模的benchmark上进行试验。

主要目标：探索一种高效的既具有局部搜索能力又有全局探索能力的元启发式算法，使用c 编程实现。

3. 研究计划与安排

第1－3周：查阅搜集文献资料，明确研究内容和课题背景，了解研究所需技术语言和开发工具，了解benchmark的要求及文件格式。确定方案，完成开题报告。

第4－6周：阅读参考文献，对问题进行建模，了解求解该问题的各种算法的特点，掌握邻域搜索的原理和步骤。

第7－10周：确定编码方案，设计数据结构及算法细节，编程实现邻域搜索、模拟退火、禁忌搜索算法。

4. 参考文献（12篇以上）

[1] 戴军. s快递公司最后一公里配送优化研究[d]. 广州: 华南理工大学, 2015.

[2] psaraftis h n. a dynamic programming solution to thesingle vehicle many-to-many immediate request dial-a-ride problem[j]. catonsville:transportation science, 1980, 14(2):130-154.

[3] nanry w p, barnes j w. solving the pickup and deliveryproblem with time windows using reactive tabu search[j]. kidlington: transportationresearch part b methodological, 2000, 34(2):107-121.

[4] li h, lim a. a metaheuristic for the pickup and deliveryproblem with time windows[c]. international conference on tools withartificial intelligence. new york: ieee, 2001:160-167.