【作者】 曹剑东；

【导师】 连小珉；

【作者基本信息】 清华大学 ， 机械工程， 2008， 博士

【摘要】 针对目前研究中存在的集送货代价描述不准确,不确定信息假设不合理,集送货动态调度方法效率较低等问题,建立评价调度方案优劣的代价函数,拟合模糊信息的隶属度曲线,设计高效的随机合理化禁忌算法、同步优化算法等,为建立高效实用的市区集送货计算机辅助调度系统打下基础。论文首先建立集送货问题的数学系统,并提出扇面Dijkstra算法完成复杂路网模型下最短路径集合的快速求解。通过模糊综合判断方法计算车厢整理代价,同时综合考虑油耗代价、折旧代价、司机代价和正常装卸代价,建立评价调度方案优劣的集送货代价函数。同时,以典型路段的交通数据和实际物流企业的业务数据为基础,拟合模糊车速和模糊发货体积的隶属度函数,在此基础上引入调度人员的主观评价指标描述集送货问题的多模糊约束条件。其次对具有模糊车速和模糊发货体积的集送货问题进行描述,提出随机合理化禁忌算法。在对线路的可行性进行分析的基础上,设计备选方案的随机合理化动态衍生方法,详细阐述基于均衡原理和代价最小原理的双特赦准则以及自适应的禁忌长度选取策略,并给出初始可行方案的快速生成方法。然后针对集送货执行过程中出现新的发货客户这一突发情况,确定动态调度的开始时刻,并引入“虚拟客户”概念将动态问题静态化。在此基础上提出将同步优化算法与顺路插入算法紧密结合,并通过模糊综合判断方法进行智能选取的求解策略,同时设计车辆位置的分段模糊递推法消除由于执行时间的不确定性带来的车辆位置变化对优化结果的影响。分析由于集送货任务变化导致调度方案无法按照原计划继续执行的情况,提出将变化客户和变化线路分开处理的两阶段应急调度算法。最后详细介绍集送货计算机辅助调度系统,并利用系统对集送货代价函数、静态调度算法和动态调度算法进行实用性验证。通过近半年时间的运行,集送货计算机辅助调度系统在稳定性、安全性、实时性等方面均能满足设计要求。更多还原

【Abstract】 In current research, costs of pickup and delivery are described not very accurately, uncertain information is assumed not very reasonably, efficiency of dynamic pickup and delivery dispatch method is not high. Therefore, cost function to evaluate dispatch solution is establlished, membership function of fuzzy information is simulated and efficient algorithms such as Random Reasonable Tabu Algorithm and Synchronized Optimization Algorithm are designed. These are all basis to design efficient and practical computer aided dispatch system for city pickup and delivery.In this thesis, mathematic system of pickup and delivery problem is set up and shortest routes set under complex road network model are fast solved by Sector Dijkstra Algorithm. Carriage arranging cost is calculated through fuzzy judgment method. Fuel cost, depreciation cost, driver cost and common load/unload cost are all taken into consideration. Therefore, cost function of pickup and delivery is established to evaluate dispatch solution. Membership function of fuzzy velocity and fuzzy pickup volume is simulated based on traffic data on typical roads and operation data in real logistics enterprise. Subjective evaluation index from dispatcher is brought in to describe multiple fuzzy restrictions in pickup and delivery problem.Second, pickup and delivery problem under fuzzy velocity and fuzzy pickup volume is described. Random Reasonable Tabu Algorithm is put forwards. Analyzing the routes feasibility, Random reasonable dynamic derivative method is designed. Dual-aspiration criterion based on equilibrium theory and minimum cost theory as well as self-adaptive Tabu length selection strategy is applied. Method that can fast create initial feasible solution is given.Third, when new pickup client comes into pickup and delivery execution process, start time of dynamic dispatch is determined. Concept of“virtual client”is assumed to turn the dynamic problem into static. Based on this, solving strategy is designed, which combines the Synchronized Optimization Algorithm and by-way insertion algorithm tightly, then selects the solution by fuzzy judgement method. Vehicle location change, which comes from uncertainty of execution time, may influence the optimization result. In order to eliminate this influence, subsection fuzzy evolutive method is designed to estimate vehicle location.The situation is analyzed, when planned solution of pickup and delivery can not be operated because tasks change.Two-phase emergency dispatch algorithm is set up, which separates changed clients and changed routes.At last, computer aided dispatch system for pickup and delivery is explained in detail. Pickup and delivery cost function, static dispatch algorithm and dynamic dispatch algorithm are validated in practice. Half a year operation of this system shows that computer aided dispatch system for pickup and delivery meets the designed requirements in stability, safety and real-time performance.更多还原