基于预约模式的出租车合乘路径优化

发布时间：2018-02-05 01:08

本文关键词： 预约打车合乘路径优化遗传算法　出处：《哈尔滨工业大学》2015年硕士论文　论文类型：学位论文

【摘要】：出租车合乘能够提高出租车的利用率,从而实现在不增加出租车投放量的前提下,一定程度上缓解当前中国大中城市打车难的问题,然而目前尚未有较为科学的模式,能够保证合乘路线的合理性并保障合乘中各方面的利益。另一方面,近年来出租车电召服务进入人们视野,并逐渐培养着人们预约打车的习惯。预约打车模式在用户需求收集方面具有先天优势,为通过优化方法实现车辆调度提供了平台与支撑。因此,研究在预约打车的背景下,根据用户出行需求,实现乘客合乘线路的优化,从而提高出租车利用率,缓解道路拥堵并减少环境污染具有一定的现实意义。本文根据出租车合乘系统的成本结构,建立了车辆合乘路径优化的数学模型,并设计了求解该模型的改进遗传算法,通过matlab对算法进行实现,分析了该模型在提高车辆利用率,降低系统成本方面的优化效果。从研究出租车预约服务模式入手,分析出租车预约用户和车辆的行为特点,研究可行的出租车预约合乘模式。分析该模式下系统的成本结构,提出了单位里程成本与载客量的三种关系模型,并根据出租车运营的实际情况确定了各个参数的取值范围,建立了带有混合时间窗的车辆路径模型用于优化合乘系统中电召车的服务路径。对比分析求解车辆路径问题的各类相关算法,确定了采用遗传算法求解该模型的思路。同时根据问题特点,设计了相应的交叉、变异等遗传操作,并将禁忌搜索算法与遗传算法混合,改进了算法的全局优化特性。处理哈尔滨市出租车GPS实际数据,通过出租车路径的起讫点识别生成用户出行需求点对,建立了优化效果测试集。通过matlab对算法进行编程,分别对比了合乘与非合乘情况下的路径优化效果,以及三种不同里程成本结构模型对优化结果的影响,最后分析了模型的参数敏感性。
[Abstract]:Taxi co-riding can improve the utilization rate of taxis, so as not to increase the number of taxis in the premise, to some extent alleviate the current problem of large and medium-sized cities in China. However, there is no more scientific model, which can ensure the rationality of the line and the interests of all aspects. On the other hand, in recent years, the taxi call service has entered the field of vision. And gradually cultivate the habit of booking taxi booking. Booking taxi mode in the user demand collection has a congenital advantage, for the optimization method to achieve vehicle scheduling platform and support. In the background of booking taxi, according to the travel needs of users, the optimization of passenger co-rider line is studied, so as to improve the utilization rate of taxis. It is of practical significance to alleviate road congestion and reduce environmental pollution. According to the cost structure of taxi ride-sharing system, the mathematical model of vehicle co-rider path optimization is established in this paper. An improved genetic algorithm is designed to solve the model. The algorithm is implemented by matlab, and the model is used to improve the vehicle utilization ratio. The optimization effect of reducing the system cost. From the study of taxi booking service mode, the behavior characteristics of taxi reservation users and vehicles are analyzed. This paper studies the feasible taxi reservation and ride model, analyzes the cost structure of the system, and puts forward three models of the relationship between the unit mileage cost and the passenger capacity. According to the actual situation of taxi operation, the value range of each parameter is determined. A vehicle routing model with a hybrid time window is established to optimize the service path of the electric vehicle in a hybrid system, and the relative algorithms for solving the vehicle routing problem are compared and analyzed. The idea of using genetic algorithm to solve the model is determined. According to the characteristics of the problem, genetic operations such as crossover and mutation are designed, and Tabu search algorithm is mixed with genetic algorithm. The global optimization characteristics of the algorithm are improved. The actual data of Harbin taxi GPS is processed and the user travel demand point pair is generated by the identification of the starting and ending points of the taxi path. The optimization effect test set is established. The algorithm is programmed by matlab, and the path optimization effect in the case of combining and non-multiplying is compared respectively. And the influence of three different mileage cost structure models on the optimization results. Finally, the parameter sensitivity of the model is analyzed.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495

【参考文献】