摘 要

近年来，物流中“最后一公里”的配送环节在电子经济中占据越来越重的地位，所带来的物流成本已不容忽视。本文针对物流中带时间窗的取送货问题展开了一定研究，并提出了两种分别基于遗传算法和模拟退火的解决方案。

在遗传算法方案中，设计了选择算子、交叉算子和变异算子，并采用了随机选点的顺序构建法。在规模为100的Benchamrk上进行了测试，结果显示在车辆数目优化上有较好的表现，并能适用客户位置呈不同类型分布的实例。

在模拟退火方案中，分别以大邻域搜索和路径重组为邻域变换操作的两个模拟退火过程交替进行。第一个过程用来减少总路程，第二个过程用来减少车辆数目。同时将顺序构建法中的随机选点方式改为依据距离优先选点的方式。相对上一方案，测试结果显示在车辆数目和总路程的优化上，都有明显改善。

本文的特色在于依据距离优先选择近点进行插入的方式大大减少了随机选择带来的无效插入次数。同时两阶段模拟退火算法有效地避免了搜索过早陷入局部最优。

关键词：遗传算法；模拟退火算法；大邻域搜索；取送货问题；顺序构建法

Abstract

In recent years, the "last mile" distribution in logistics has occupied an increasingly important role in the electronic economy, by which the logistics costs brought can’t be ignored. In this paper, the pickup and delivery problem with time of this problem is studied and two solutions based on genetic algorithms and simulated annealing are given.

In the genetic algorithm scheme, the selection operator, the crossover operator and the mutation operator are designed, and the sequential construction method based on random selection is adopted. The result obtained from the test on the benchmarks with the scale of 100 shows that the scheme has a better performance in the optimization of the number of vehicles, and can be applied to all benchmarks with different types of distribution.

In the simulated annealing scheme, two simulated annealing processes with large neighborhood search and path recombination been the neighborhood transformation operation respectively, are performed alternately. The first process is used to reduce the total distance, and the second process is used to reduce the number of vehicles. At the same time, the random selection method in the sequential construction method is changed to the method of distance preference. In contrast to the previous scheme, the test results show a significant improvement in the number of vehicles and the optimization of the total distance.

The feature of this paper is that the way in which request is preferentially selected according to the distance to be inserted into the path greatly reduces the number of invalid inserts caused by random selection. At the same time, the two-stage simulated annealing algorithm effectively avoids searching for local optimizations.

Key Words：Genetic Algorithm；Simulated Annealing；Large Neighborhood Search；Pickup and Delivery Problem；Sequential Construction

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 课题背景和意义 1

1.2 课题研究综述 1

1.2.1 PDPTW问题 1

1.2.2 国内外研究现状 2

1.3 论文主要内容 3

第2章 PDPTW问题数学建模 4

2.1 问题描述 4

2.2 目标函数 5

2.3 模型建立 6

2.4 本章小结 7

第3章 遗传算法方案 8

3.1 编码方案 8

3.2 交叉算子 9

3.3 变异算子 10

3.4 选择算子 10

3.5 随机选点的顺序构建法 11

3.6 爬山算法 13

3.7 算法框架 14

3.8 实验结果 14

3.9 本章小结 16

第4章 模拟退火方案 17

4.1 模拟退火算法 17

4.2 大邻域搜索算法 18

4.3 路径重组 18

4.4 按距离优先选点的顺序插入法 19

4.5 温度参数设计 20

4.6 算法框架 20

4.7 实验结果 22

4.8 本章小结 26

第5章 总结与展望 28

5.1 工作总结 28

5.2 研究展望 28

参考文献 29

附 录 31

致 谢 41