WallaceHu的个人博客分享 http://blog.sciencenet.cn/u/WallaceHu

博文

车辆路径优化的,看过来:双边装卸,最低耗能,全新进展

已有 3335 次阅读 2016-12-5 16:48 |个人分类:科研论文|系统分类:论文交流

注:部分采英文陈述,一是基于原始引用,二是本人不知其准确翻译。不便之处,还请见谅!


在运筹学领域,Travel Salesman Problem (TSP) 是大家熟知的科学问题。根据维基百科:The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.


后来,人们发现很多的路径优化问题都可以看做是TSP问题的变体,即增减了约束或采用了新的优化目标。其中,the pickup and delivery problem (PDP)问题便是这样一类问题。在研究PDP的问题中,人们很早便已开始考虑有装卸约束的情况。但,几乎都是经典的约束情况,即,先进先出或先进后出的装卸约束。


从2011年底至2013年初,我们研究了一类新的PDP问题。该问题源于货运机场终端的一个实际问题(见图1):具有双边装卸能力的自动有轨电车,根据调度算法,将在轨道两边的货物以最高效的方式运送到轨道两边其它的位置,再由同一轨道上或者是不同轨道上的其它自动有轨电车,接力将货物运送到最终目的地。


图1:单个自动有轨电车的工作区域图


我们将高效定义为,有轨电车消耗的电能最低(有别于传统的路径或时间最短——不意味着耗能最小)。并将服务的质量要求定为约束条件,如取、送的时间窗口。由于电车能同时运送多个货物,可以从轨道两边装、卸,而且货物的目的地分布在轨道两边,而货物一旦装上便不可以在车内易位(即左右位置的货物在车内不可以互换位置)。目前应用的算法,是一类调度算法和supervisory control结合的算法;前者无法保证所提供的解是逻辑可行的,后者用于后验地避免不可行解。该算法总体性能欠佳,无法优化运输耗能。


我们对该问题进行了全面的建模,建模中引入了一系列新的约束,以刻画问题中所出现的复杂逻辑条件,以避免任何可能的装卸冲突。所得优化模型可在满足所有实际约束条件下,优化装、卸货物的顺序,以最小化总体的运输耗能。最后,该优化模型结合滚动优化,以处理实际中货物动态到达的情况。


详情请阅读论文:http://www.sciencedirect.com/science/article/pii/S0377221716307159

或者预印本(最终版以上面的链接为准):https://arxiv.org/abs/1502.01452


所研究的问题及其优化模型,可为古老的车辆路径优化问题,添加绿意。或启迪新的相关研究。

新的模型处理复杂的逻辑约束,或给您的研究带来灵感!




https://blog.sciencenet.cn/blog-3008991-1018849.html

上一篇:暖博:以文会友,雅俗共赏
收藏 IP: 192.122.131.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 19:54

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部