近年来,为了避免环境污染,很多国家制定了相应的法律法规,要求企业对
整个产品的生命周期负责,不仅要提供客户满意的配送服务,还要进行废弃物的
回收利用。因此,企业有了构建正向物流配送和逆向废旧物品回收相结合的物
流系统的迫切需求;而客户往往只在特定的时间窗内接受服务。为了提升服务
质量和客户满意度,企业不仅需要完成同时送取货的作业,还要额外考虑客户的
服务时间窗。因此,如何设计出合理完善的带时间窗的双向物流系统,成为理论
研究和实践中关注的重要问题。在运筹学领域,该类问题被称为带时间窗和同
时 送 取 货 的 车 辆 路 径 问 题 （ vehicle routing problem with simultaneous
delivery-pickup and time windows,VRPSDPTW）。
VRPSDPTW 问题作为车辆路径问题（vehicle routing problem,VRP）的
重要扩展,属于 NP-hard 问题。这类问题的解决方法主要分为精确算法和启发
式算法。2002 年,Angelelli 等
[1]
最早提出 VRPSDPTW 问题,使用精确算法中的
分支-价格法求解算例规模为 20 个客户点的小型算例。当客户规模增大时,精
确算法不能在合理的时间范围内求得满意解。学者们开始尝试设计不同的启发
式算法来解决 VRP-SDPTW 问题。Cao 等
[2]
提出了一种改进的遗传算法,根据
用户的优先顺序重新设计了编码方式。当最大客户数目为 8 时,改进算法能有
效找到最优解,然而,在现实生活中,客户数目远远多于 8 个。Boubahri 等
[3]
设计
了一个多智能体群体系统来解决 VRPSDPTW 问题。尽管这种解决方法很新颖,
但是作者没有提供任何数值实验结果。2012 年,Wang 等
[4]
采用协同进化遗传算
法 解 决 VRPSDPTW 问 题 , 并 在 经 典 的 Solomon 数 据 集 的 基 础 上 设 计 了
VRPSDPTW 基准实例,实验结果表明,所提出的协同进化遗传算法能够在较短
的时间内找到满意解。王超等
[5]
运用回溯搜索优化算法来求解该问题,选取了测
试数据集中的 6 个算例进行了实验。王超等
[6]
提出了一种离散布谷鸟算法来求
解该问题。除此之外,还有改进全局人工鱼群算法
[7]
、大邻域搜索算法
[8]
等。
目前关于 VRPSDPTW 问题,虽然学者们已经进行了一些研究,但是仍然缺
乏有效的求解方法。迄今为止,VRPSDPTW 问题的解决,主要采用启发式算法,
并且以 Wang 等设计的测试数据集作为国际通用数据集,各类文献中的已知算
法在对算例进行测试时,都无法找到所有算例的最优解,因此,高效、稳定的求解
方法成为学者们追求的目标。
剩余18页未读，继续阅读
罗伯特之技术屋
- 粉丝: 4438
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减5.97元 开通VIP
相关推荐
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0
最新资源