热门搜索: 论文 发表 社科期刊 北大核心 南大核心 cssci 科技期刊 教育

当前位置:主页 > 经济论文 > 电子商务论文 >

带时间窗快递车辆路径问题模型及算法研究

发布时间:2019-01-11 18:19  文章来源:笔耕文化传播
【摘要】:随着电子商务的飞速崛起,快递企业如何合理安排运输车辆以降低运输成本成为一个迫切需要解决的问题。快递车辆路径问题是经典的车辆路径问题(Vehicle Routing Problem, VRP)的变种,也是一个NP难问题。因此,快速的启发式求解算法及解好坏的评估是研究中的难点和关键。该问题的研究及应用,可以显著地降低快递行业的运输成本,同时也减少车辆的二氧化碳排放量,对经济和环境产生积极影响。给定分拨中心的网络结构及其服务时间窗口约束和各个分拨中心之间的货物流量结构及其时效约束的快递车辆路径规划,是实际中最为常见的一类问题。本文主要研究了带时间窗的快递车辆路径问题的建模及求解,具体工作包括以下两项内容:1.固定时间窗快递车辆路径问题建模及求解固定时间窗快递车辆路径问题就是研究在收件时间窗和派件时间窗固定的情况下,如何安排班车路由使得班车花费的总成本最小。本文首先建立了此问题的数学模型,然后设计了基于贪心启发式方法的快速求解算法,并提出了一种新的班车安排方法:环线班车+单边车,以此代替原有的效果较差的对称班车安排方法,最后还给出了评估该问题解的一个下界模型。通过在不同规模的真实数据集上进行计算实验,将提出算法的求解结果与下界模型得到的下界进行比较,从而表明了求解算法的精确程度。还将两种班车安排方法得到的结果进行对比,说明了本文提出的新班车安排方法优于原有班车安排方法。此外,对于9城市数据和21城市数据,求解算法总的计算时间分别为1秒和54秒。2.可变时间窗快递车辆路径问题建模及求解通过分析发现时间窗对于班车运输成本影响较大,为此需要将时间窗作为可变参数纳入到模型中,我们将该问题称之为可变时间窗快递车辆路径问题。本文在固定时间窗问题的基础上,采用环线班车+单边车的班车安排方法,建立了该问题的数学模型。为了评价算法求解结果的优劣,对该问题建立了时间约束松弛的下界模型并加以证明,再采用Lingo软件求出其一个下界。最后,设计了一种两阶段的求解算法,该算法包括时间窗求解和固定时间窗问题求解两个阶段,并且在时间窗求解阶段设计了时间窗口好坏的一个评价函数。在9城市数据集和21城市数据集上分别进行了求解,计算结果表明,时间窗口的好坏对最终班车安排花费有较大的影响,一组良好的时间窗口安排可以有效的降低班车运输成本。
[Abstract]:With the rapid rise of electronic commerce, how to arrange the transportation vehicle reasonably to reduce the transportation cost becomes an urgent problem to be solved by express delivery enterprises. Express vehicle routing problem is a variant of the classic vehicle routing problem (Vehicle Routing Problem, VRP), and is also a difficult NP problem. Therefore, the fast heuristic algorithm and the evaluation of the solution are the difficulties and key points in the research. The research and application of this problem can significantly reduce the transport cost of the express delivery industry, but also reduce the carbon dioxide emissions of vehicles, and have a positive impact on the economy and the environment. It is the most common problem in practice that the network structure of the distribution center and its service time window constraints, the cargo flow structure between the distribution centers and its time-limited express vehicle routing planning are the most common problems in practice. This paper mainly studies the modeling and solution of express vehicle routing problem with time window. The specific work includes the following two parts: 1. Modeling and solving the fixed time window Express vehicle routing problem is to study how to arrange the routing of the shuttle bus to minimize the total cost of the shuttle bus when the pickup time window and the distribution time window are fixed. This paper first establishes the mathematical model of the problem, then designs a fast solution algorithm based on greedy heuristic method, and proposes a new method of arranging the bus: the one-sided car of the loop line bus. A lower bound model for evaluating the solution of the problem is given. Through the calculation experiments on real data sets of different scales, the results of the proposed algorithm are compared with the lower bound obtained by the lower bound model, which shows the accuracy of the algorithm. The results obtained from the two methods are compared and the results show that the new method is superior to the original one. In addition, for 9 city data and 21 city data, the total computation time of the algorithm is 1 second and 54. 2 seconds, respectively. Modeling and solving of variable time window Express vehicle routing problem through analysis, it is found that time window has a great influence on the transportation cost of shuttle bus, so it is necessary to incorporate time window into the model as a variable parameter. We call this problem a variable time window express vehicle routing problem. On the basis of the fixed time window problem, the mathematical model of the problem is established by using the method of arranging the single side car of the circular line bus. In order to evaluate the advantages and disadvantages of the algorithm, a lower bound model of time-constrained relaxation is established and proved, and a lower bound is obtained by using Lingo software. Finally, a two-stage algorithm is designed. The algorithm consists of two stages: time window solution and fixed time window solution, and an evaluation function of time window is designed in the time window solution phase. The results on 9 city data sets and 21 city data sets show that the time window has a great influence on the cost of the final schedule. A good time window arrangement can effectively reduce the transportation costs.
【学位授予单位】:中国科学技术大学
【学位级别】:硕士
【学位授予年份】:2016
【分类号】:TP301.6

【相似文献】

相关期刊论文 前10条

1 唐加福;孔媛;潘震东;董颖;;基于划分的蚁群算法求解货物权重车辆路径问题[J];控制理论与应用;2008年04期

2 钟雪灵;王雄志;;开放式车辆路径问题的混合算法[J];计算机仿真;2011年08期

3 熊浩;符卓;鄢慧丽;;动态车辆路径问题的隐分区灵活分批策略[J];同济大学学报(自然科学版);2013年05期

4 娄山佐;吴耀华;肖际伟;廖莉;;基于增强学习解决随机需求车辆路径问题[J];系统仿真学报;2008年14期

5 徐俊杰;;车辆路径问题的改进微正则退火算法[J];信息化纵横;2009年06期

6 吴斌;邵建峰;方叶祥;;基于客户满意度的开放式车辆路径问题研究[J];计算机工程;2009年17期

7 王江晴;张潇;;复杂环境下动态车辆路径问题的建模与求解[J];武汉大学学报(理学版);2010年04期

8 陆琳;蔡绍洪;;一类随机顾客车辆路径问题及其算法[J];南京航空航天大学学报;2010年04期

9 温惠英;孙博;;协同车辆路径问题的模糊规划模型和算法[J];计算机应用研究;2011年02期

10 杨皎平;高雷阜;王俊;;装卸联盟车辆路径问题及两阶段优化方法[J];计算机工程与应用;2011年14期

相关会议论文 前10条

1 符卓;陈斯卫;;车辆路径问题的研究现状与发展趋势[A];中国运筹学会第七届学术交流会论文集(下卷)[C];2004年

2 杨世坚;陈韬;;随机车辆路径问题研究综述[A];中国系统工程学会决策科学专业委员会第六届学术年会论文集[C];2005年

3 李桂平;陈楠;;多中心车辆路径问题的解决思路[A];中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集[C];2007年

4 李大卫;王梦光;;广义车辆路径问题——模型及算法[A];1997中国控制与决策学术年会论文集[C];1997年

5 符卓;聂靖;;开放式车辆路径问题及其若干研究进展[A];中国运筹学会第八届学术交流会论文集[C];2006年

6 陈宝文;宋申民;陈兴林;单志众;;应用于车辆路径问题的多蚁群算法[A];第25届中国控制会议论文集(下册)[C];2006年

7 戎丽霞;;模糊需求条件下的多车场车辆路径问题[A];第三届中国智能计算大会论文集[C];2009年

8 张凤姣;张兴芳;;基于不确定理论的车辆路径问题[A];第九届中国不确定系统年会、第五届中国智能计算大会、第十三届中国青年信息与管理学者大会论文集[C];2011年

9 肖雁;符卓;李育安;;带软时间窗的车辆路径问题及其应用前景探讨[A];中国运筹学会第六届学术交流会论文集(下卷)[C];2000年

10 许鑫;范文慧;冯雅U,

本文编号:2407319


论文下载
论文发表
教材专著
专利申请


    下载步骤:1.微信扫码,备注编号 2407319. 2.自助下载


    本文链接:http://www.bigengculture.com/jingjilunwen/dianzishangwulunwen/2407319.html