【作者】 唐连生；

【导师】 程文明；

【作者基本信息】 西南交通大学 ， 机械设计及理论， 2008， 博士

【摘要】 车辆路径问题是物流管理研究中的一项重要内容,有效解决车辆路径问题不仅可以降低物流配送成本,还能提高客户个性化需求的响应速度、服务质量和客户对物流配送服务的满意度。突发事件容易引起交通堵塞,造成路网中断,增加车辆行程时间,从而引发基于连通可靠性和行程时间可靠性车辆路径问题,极大地增加了物流运输成本,严重损害物流企业的利益,同时还可能引起社会应急救援物流配送及伤病员转移等一系列问题。传统的车辆路径问题模型往往忽略突发事件对配送服务可靠性的影响,使用平均行程时间作为其车辆路线规划前提,在突发事件背景下是无法真正满足这种要求的。要想合理地反映突发事件下物流配送车辆路线的随机动态性特征,必须构建能够考虑诸多因素的车辆路径问题模型,引入路网可靠性进行分析,从而使模型更贴近实际运行情况。借用路网可靠性的多种概率性能指标,反映物流配送系统的运行特征,为客户定制符合“个性化”需求的物流方案,借此提高物流企业的市场竞争优势。本文就突发事件引起的基于连通可靠性、行程时间可靠性和应急物流配送的车辆路径问题进行了深入研究,主要研究内容如下:(1)针对基本蚁群算法求解车辆路径问题时收敛速度慢的问题,提出了一种快速收敛的蚁群算法,利用车辆满载率作为调节因子来控制信息素的变化,使其尽快寻找到最优路径。同基本蚁群算法相比较,在收敛速度和求解质量上具有明显的优越性。(2)提出了突发事件前提下基于连通可靠性的车辆路径问题和基于行程时间可靠性的车辆路径问题数学模型,利用蚁群算法中状态转移概率公式,将连通可靠性、行程时间可靠性问题与蚁群算法结合,应用到突发事件下的车辆路径问题中,丰富了车辆路径问题的内容。同时根据问题性质不同设置相应参数,丰富了蚁群算法的参数设定。通过实例分析探索了各参数取值对结果的影响及其合理设定。(3)旅行时间直接影响到顾客对物流配送服务的满意度,具有模糊旅行时间的车辆路径问题应考虑模糊约定时间对客户满意度影响,应用线性加权法综合多个目标函数,通过实例分析了蚂蚁算法参数取值对结果的影响。(4)针对突发事件下灾难发生时应急物流的特点,提出了一种用于解决突发事件下物流配送车辆路径多目标优化问题的蚁群聚类优化算法。结合蚁群的墓地构造行为特点,利用改进LF蚁群聚类模型,以节点需求未得到满足的不满意度最小和路由时间最短为优化目标,应用线性加权方法将多目标问题转化为单目标问题,用LF蚁群聚类方法按约束条件进行聚类,最终确定车辆具体的出行线路。目前突发事件下车辆路径问题的研究刚刚起步,其适用性还未能被实际应用证实,求解的技术也远没有达到成熟的地步。但是,基于连通可靠性和行程时间可靠性的分析必然会给物流行业带来深远的影响。结合我国的国情,将路网可靠性理论与车辆路径问题有机结合,可以在很大程度上改善现有的物流服务状况,提高国家的抗灾救援能力,具有广阔的实际应用前景。随着智能交通系统的发展,将群集智能技术应用于物流规划问题同样具有重要的理论和现实意义。更多还原

【Abstract】 Vehicle routing problem is an important study element of logistics management, which solved effectively, can not only reduce distribution costs, but also increase the responsiveness speed for individuation requirement of customer, service quality and customer satisfaction for logistics and distribution service. Emergencies caused by traffic congestion, road network disruption and increased travel time would greatly increase the cost of logistics, seriously damaged the interests of logistics enterprises, and also lead to social emergency logistics and distribution and transfer of sick and wounded, and other issues. The traditional model of vehicle routing problem often neglected emergencies on the reliability of distribution service, if only using average travel time as a precondition for vehicle routing planning; in emergencies can not really meet the requirements. To reflect the stochastic and dynamic charactorics of distribution vehicle routing reasonable, we must consider more factors to build the vehicle routing problem model by introducing reliability, so that the model can be closer to the actual operation. By using various performance indicators of the network reliability, the operation features of logistics distribution system can be embodied, which tailored to special customers in order to satisfy their requirements as well as en enhancing the market competition of logistics enterprises.The main study of this paper as follows:(1) Aim to the slow convergence of basic ant colony algorithm for vehicle routing problem, a fast convergence method is proposed by using vehicle loaded rate as a regulator to control pheromone changing so that the ant can find the optimal path as soon as possible. Compared with the basic ant colony algorithm, the convergence speed and solution quality is obviously superiority in this thesis.(2) Mathematical model of vehicle routing problem based on the connectivity reliability and travel time reliability are proposed. By using ant algorithm the state transition probability formula in the ant colony algorithm, combining with connectivity reliability and travel time reliability are applicated to the vehicle routing problem under emergency, which enrich the content of vehicle routing problem. At the same time, additional parameters are added in accordance with the different nature of the problem, enriching the parameters set of ant colony algorithm. By an example, analysing and exploring how to set the values of the parameters effect on the results, which influences the reasonably setting of parameters.(3) Travel time directly impacts on customer satisfaction with the logistics and distribution services. Vehicle routing problem with fuzzy travel time should consider the impact of ambiguous appointed time on customer satisfaction. We integrate multiple objective functions applicating linear weighted weighted method, and analyse result through because of the ant colony algorithm parameters through an example.(4) According to emergency logistics characteristics when disaster happened, a solution for emergency distribution of multi-objective optimization problem based on ant cluster optimization algorithm is proposed. Multi-objective problem is transformed into a single one using linear weighted method. With the ant behavior characteristics in constructuring graves, by using improved LF ant clustering model, taking minimize dissatisfied node need and shortest travel time as the optimization objective, clustering with the constrains by LF ant clustering method, the vehicle routing lines are determined finally.The study of vehicle routing problem under emergency has just begun, its applicability has not been proved by practical application, and technology to solve is beyond a mature stage. However, based on connectivity reliability and travel time reliability of the logistics industry is beyond impact in this field. With national conditions, the network reliability theory integrate with vehicle routing problem, which in large improve the existing state of logistics services, has broad practical application prospaction. With the development of intelligent transportation systems, swarm intelligence technology will be applied to logistics planning and the great theoretical and practical significance could be expected.更多还原