需求不确定的车辆路径问题模型与算法研究

摘要

交通与物流是支撑社会经济发展的重要行业，车辆路径问题(Vehicle RoutingProblem，VRP)作为组合优化和运筹学领域研究的经典和热点问题，主要研究在满足一定约束条件下合理安排车辆的路径方案和调度计划，使得总体的配送服务成本达到优化，其在物资调运、电子商务以及铁路民航、公交线路等交通和物流领域具有极为广阔的应用背景，而在现实生活中，经常出现某些信息无法提前获知的情况，属于不确定问题，因此对贴近实际生产作业环节中的不确定型车辆路径问题进行研究和优化具有较强的理论和现实意义。本文以模糊需求车辆路径问题（Capacitated Vehicle Routing Problem with Fuzzy Demand，CVRPFD）、随机需求车辆路径问题（Capacitated Vehicle Routing Problem with Stochastic Demand，CVRPSD）、动态需求车辆路径问题(Capacitated Vehicle Routing Problem with Dynamic Requests，CVRPDR)为例，对需求不确定型车辆路径问题展开研究。 在对不确定规划理论、VRP研究进展以及启发式算法进行综述的基础上，首先分析了经典的CVRP，设计结合变邻域搜索和生物共栖搜索的混合启发式算法求解，算法采取有序编码方式，通过文献算例对比验证和分析表明了混合算法以及模型的有效性。 针对CVRPFD，基于先预优化后重调度的两阶段求解思路，本文首先分析和处理了CVRPFD的客户点模糊需求变量，通过引入模糊可信性理论，结合预设的决策者风险偏好水平，该模糊变量可以通过模糊机会约束参与后续优化环节。依据所构建的CVRPFD模糊机会规划模型，本文设计了两阶段求解混合变邻域禁忌搜索算法，提出了新客户点重调度策略，该策略能解决以往失败点返回先天不足以及适当返回点选取困难的问题，在出现路径失败时依据重调度策略对全部未完全服务子路径展开整体优化，降低额外配送成本，保证所有客户点能接受服务。 针对CVRPSD，本文首先对客户点处随机需求变量进行了分析和处理，构建随机机会约束使其可以参与模型优化，随后依据中心极限定理对该约束进行了确定型等价处理，使后续失败路径的调整得以进行。由于随机需求变量的影响，CVRPSD在求解时也有两阶段优化的特点，预优化阶段首先借助随机机会约束规划模型求得路径方案，在出现路径失败时依据所提出的失败点重调度策略重新调整方案，减少额外配送成本。文章设计了结合变邻域搜索和分散搜索的混合算法对CVRPSD展开两阶段优化求解，通过时间复杂性分析和相应确定型CVRP算例、CVRPSD随机问题算例和文献对比分析表明了所构建随机机会约束规划模型以及混合算法的有效性，算例结果表明新的失败点重调度策略能有效减少整体的配送成本。 在对模糊和随机因素影响下UVRP进行研究基础上，本文对CVRPDR展开了相关研究，不同于前两个问题两阶段优化的特征，客户点动态需求的特点使得CVRPDR必须通过周期性的多阶段优化来实现求解，其优化策略对最终方案总成本影响较大。文章首先对其动态性进行了分析，随后提出了基于时间片划分的周期性实时重置策略来解决客户点连续出现的问题，其延迟服务机制能均衡新老客户点的服务需求，合理利用时间因素优化客户点服务顺序，减少车辆配送成本。依据上述策略，文章还设计了子路径动态转变的混合变邻域人工蜂群算法来求解CVRPDR，该算法中车辆子路径可在时间片间动态转变，客户点能实现与虚拟中心的转变，契合动态问题的求解特征。

目录

声明

摘要

引言

第1章绪论

1．1研究背景和意义

1．2研究思路和方法

1．2．1研究思路

1．2．2研究方法

1．3研究内容和章节结构

1．3．1研究内容

1．3．2章节结构

第2章相关理论及研究综述

2．1不确定规划理论

2．1．1模糊机会约束规划

2．1．2随机机会约束规划

2．2确定型车辆路径问题研究综述

2．2．1标准车辆路径问题描述及模型

2．2．2车辆路径问题要素构成

2．2．3确定型车辆路径问题分类

2．3不确定型车辆路径问题研究综述

2．3．1不确定型车辆路径问题概述

2．3．2模糊车辆路径问题研究综述

2．3．3随机车辆路径问题研究综述

2．3．4动态车辆路径问题研究综述

2．3．5存在的问题

2．4启发式算法

2．4．1变邻域搜索算法

2．4．2生物共栖搜索算法

2．4．3禁忌搜索算法

2．4．4分散搜索算法

2．4．5人工蜂群算法

2．5小结

第3章容量约束车辆路径问题优化

3．1 CVRP问题描述及整数规划模型构建

3．1．1CVRP问题描述和基本假设

3．1．2整数规划模型构建

3．2混合变邻域生物共栖搜索算法设计

3．2．1混合启发式算法框架

3．2．2生物共栖搜索算法

3．2．3解方案编码及解码

3．2．4共栖搜索算子

3．2．5变邻域搜索策略

3．2．6混合算法计算复杂度分析

3．3算例验证及结果分析

3．4小结

第4章模糊需求车辆路径问题优化

4．1 CVRPFD问题描述及模糊机会约束规划模型构建

4．1．1 CVRPFD问题描述和基本假设

4．1．2模糊机会约束规划模型构建

4．2预优化变邻域禁忌搜索算法设计

4．2．1混合启发式算法框架

4．2．2初始种群生成及优化

4．2．3变邻域搜索策略

4．2．4禁忌搜索设置

4．3客户点重调度策略优化调整

4．3．1随机模拟算法

4．3．2客户点返回策略

4．3．3客户点重调度策略

4．4算例验证及结果分析

4．4．1确定型CVRP算例验证

4．4．2 CVRPFD模糊算例预优化方案求解验证

4．4．3 CVRPFD客户点重调度策略验证

4．5小结

第5章随机需求车辆路径问题优化

5．1 CVRPSD问题描述及随机机会约束规划模型构建

5．1．1 CVRPSD问题描述和基本假设

5．1．2随机机会约束规划模型构建

5．1．3随机机会约束确定型等价处理

5．2预优化混合变邻域分散搜索算法设计

5．2．1混合启发式算法框架

5．2．2初始种群生成及多样性优化

5．2．3参考集更新及子集对组合策略

5．2．4变邻域搜索策略

5．3失败点重调度策略优化调整

5．3．1失败点返回策略

5．3．2失败点重优化策略

5．3．3混合算法两阶段求解时间复杂性分析

5．4算例验证及结果分析

5．4．1确定型CVRP算例验证

5．4．2 CVRPSD随机算例验证

5．5小结

第6章动态需求车辆路径问题优化

6．1动态需求车辆路径问题描述及模型构建

6．2 CVRPDR动态性分析及客户点实时重置策略

6．2．1CVRPDR动态性分析

6．2．2基于周期性优化的客户点实时重置策略

6．3子路径动态转变的混合变邻域人工蜂群算法设计

6．3．1混合启发式算法框架

6．3．2解方案构造及时问片动态信息更新

6．3．3人工蜂群操作及变邻域搜索改进

6．3．4混合算法时间复杂性分析

6．4算例验证及结果分析

6．4．1车辆启动延迟系数灵敏度分析

6．4．2 CVRPDR动态算例验证

6．5小-结

第7章结论与展望

7．1结论

7．2展望

参考文献

攻读学位期间公开发表论文

致谢

作者简介