A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.      

Vehicle routing with stochastic time-dependent travel times

Assigning and scheduling vehicle routes in a stochastic time-dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic. Our methodology builds on earlier work in which the traffic congestion is captured in an analytical way using queueing theory. The congestion is then applied to the VRP problem. In this paper, we introduce the variability in traffic flows into the model. This allows for an evaluation of the routes based on the uncertainty involved. Different experiments show that the risk taking behavior of the planner can be taken into account during optimization. As more weight is given to the variability component, the resulting optimal route will take a slightly longer travel time, but will be more reliable. We propose a powerful objective function that is easily implemented and that captures the trade-off between the average travel time and its variance. The evaluation of the solution is done in terms of the 95th-percentile of the travel time distribution (assumed to be lognormal), which reflects well the quality of the solution in this stochastic time-dependent environment.     

A note on the square root law for urban police travel times

The classical Square Root Law formula for emergency travel times consists of one observable component, the density of patrol coverage, and one unknown component that must be estimated empirically, the effective travel speed. The effective travel speed is typically assumed to be an empirical constant. We test whether this simplifying assumption is justified empirically. We propose a modern machine-learning approach and a Least Absolute Shrinkage and Selection Operator regression to incorporate into a travel speed model various exogenous factors such as call type, incident location, weather conditions and traffic congestion. The value of the proposed analytical approach and some practical implications are demonstrated using operational data from a large urban police jurisdiction based in British Columbia, Canada. Although the analysis is framed within the context of urban emergency police operations, the proposed approach has the potential to be useful for other emergency services or roving business units that deal with unscheduled service calls.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

Optimizing departure times in vehicle routes

Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. In practice, however, temporary traffic congestion make such solutions non-optimal with respect to minimizing the total duty time. Furthermore, the VRPTW does not account for driving hours regulations, which restrict the available travel time for truck drivers. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing of a VRPTW. We propose an ILP formulation that minimizes the total duty time. The results of a case study indicate that duty time reductions of 15% can be achieved. Furthermore, computational experiments on VRPTW benchmarks indicate that ignoring traffic congestion or driving hours regulations leads to practically infeasible solutions. Therefore, new vehicle routing methods should be developed that account for these common restrictions. We propose an integrated approach based on classical insertion heuristics.     

Short-term forecasting of traffic delays in highway construction zones using on-line approximators

Highway construction zones are often the cause of traffic delays. This is a natural consequence of the high congestion and nonuniform traffic flow conditions in construction zones. Most of the current algorithms for computing traffic delays are accurate for low density traffic conditions, and address the estimation of current travel time only. This paper presents a method for short-term forecasting of traffic delays in highway construction zones using data from presence detectors. The method is based on a modular approach wherein data from adjacent detectors is processed for estimating the travel time between the two detectors. The travel time estimates are then considered as time-series data, and the problem of short-term forecasting of traffic delay is formulated as a time-series evolution problem. A generic structure referred to as an on-line approximator is used for the prediction of travel time based on current and past travel time estimates. Simulation examples are used to illustrate the traffic delay forecasting algorithm.     

A dynamic route guidance system based on real traffic data

Mobility is one of the vital goods of modern societies. One way to alleviate congestion and to utilise the existing infrastructure more efficiently are Advanced Traveller Information Systems (ATIS). To provide the road user with optimal travel routes, we propose a procedure in two steps. First on-line simulations supplemented by real traffic data are performed to calculate actual travel times and traffic loads. Afterwards these data are processed in a route guidance system which allows the road user an optimisation with regard to individual preferences. To solve this multiple criteria optimisation problem fuzzy set theory is applied to the dynamic routing problem.     

基于SD-GM理论的城市交通拥堵收费模型研究

随着中国城市化建设步伐的不断加快,交通拥堵在不断地加剧。同时,因机动车污染物的排放,每年将产生大量的NO_x,从而又会引起严重的大气污染(如“雾霾”污染)。针对这些问题,本文从环境和社会的角度出发,采用系统动力学与灰色系统相结合的方法(SD-GM),构建了城市交通拥堵收费模型,并对模型中主要变量进行动态仿真和决策分析,以此来寻找缓解交通拥堵和减少机动车尾气排放的可行策略。通过现实性测试和敏感性测试,得到拥堵收费的范围不超过100元/天*辆。通过进一步的仿真和结果分析可得到以下结论:(1)在区间[25,40] 内,随着拥堵收费的提高,NO_x存量,机动车出行吸引度和交通拥堵程度都呈下降趋势,而车均道路面积呈上升趋势。(2)但并非拥堵收费越高越好, 超过40 元/天*辆,会产生相反的效果。最后,通过比较分析,得到NO_x存量,机动车出行量,机动车出行吸引度和交通拥堵程度分别下降了约33.76%,39.64%,43.26%,82.25%,而车均道路面积提高了大约65.68%,进而验证了模型的有效性和实用性。     

A network-consistent time-dependent travel time layer for routing optimization problems

In the vehicle routing literature, there is an increasing focus on time-dependent routing problems, where the time (or cost) to travel between any pair of nodes (customers, depots) depends on the departure time. The aim of such algorithms is to be able to take recurring congestion into account when planning logistics operations. To test algorithms for time-dependent routing problems, time-dependent problem data is necessary. This data usually comes in the form of three-dimensional travel time matrices that add the departure time as an extra dimension. However, most currently available time-dependent travel time matrices are not network-consistent, i.e., the travel times are not correlated both in time and in space. This stands in contrast to the behavior of real life congestion, which generally follows a specific pattern, appearing in specific areas and then affecting all travel times to and from those areas. As a result of the lack of available network-consistent travel time matrices, it is difficult to develop algorithms that are able to take this special structure of the travel time data into account.     

Advanced routing for city logistics service providers based on time-dependent travel times

Increasing traffic demand, recurring congestion and sophisticated e-commerce business models lead to enormous challenges for routing in city logistics. We introduce a planning system for city logistics service providers, which faces those challenges by more realistic vehicle routing considering time-dependent travel times. Time-dependent travel times arise from telematics-based traffic data collection city-wide. Well-known heuristics for the Traveling Salesman Problem and for the Vehicle Routing Problem are adapted to time-dependent planning data. Computational experiments allow for insights into the efficiency of individual heuristics, their adaptability to time-dependent planning data sets, and the quality and structure of resulting delivery tours.     

Journey time estimation using single inductive loop detectors on non-signalised links

This paper describes two techniques designed to estimate vehicle journey times on non-signalised roads, using 250?ms digital loop-occupancy data produced by single inductive loop detectors. A mechanistic and a neural network approach provided historical journey time estimates every 30?s, based on the data collected from the previous 30?s period. These 30?s estimates would provide the traffic network operator with immediate post-event congestion information on roads where no close circuit television cameras were present. The mechanistic approach estimated journey times every 30?s between pairs of detectors, using the knowledge of vehicle speed derived from the loops and the distances between them. The 30?s average loop-occupancy time per vehicle, average time-gap between vehicles and percentage occupancy parameters derived from the inductive loops were presented to a neural network for training along with the associated vehicles' measured journey times. The neural network was shown to consistently out-perform the mechanistic approach (in terms of the mean absolute percentage deviation from the mean measured travel time), particularly when using pairs of detectors.     

大数据背景下基于5S的城市交通拥堵评价模型研究

近几年来,城市交通拥堵问题日益突出,极大制约了城市发展。在大数据背景下,为了准确掌握交通实时拥堵状况,改善城市交通,便利市民出行,本文深入挖掘城市交通拥堵的影响因素,构建了基于交通5S要素的城市拥堵理论模型,运用径向基函数神经网络方法工具,以上海静安寺、上海站、陆家嘴周围三大拥堵路段的交通数据集为例,验证了该模型的有效性。实验结果表明,由该模型获得的城市交通拥堵预测值与上海实际交通路况具有较好的拟合效果,表明交通5S模型与方法能够准确有效地评价城市交通拥堵。     

Modeling traffic flow interrupted by incidents

A steady-state M/M/c queueing system under batch service interruptions is introduced to model the traffic flow on a roadway link subject to incidents. When a traffic incident happens, either all lanes or part of a lane is closed to the traffic. As such, we model these interruptions either as complete service disruptions where none of the servers work or partial failures where servers work at a reduced service rate. We analyze this system in steady-state and present a scheme to obtain the stationary number of vehicles on a link. For those links with large c values, the closed-form solution of M/M/∞ queues under batch service interruptions can be used as an approximation. We present simulation results that show the validity of the queueing models in the computation of average travel times.     

Dynamic system optimal performances of shared autonomous and human vehicle system for heterogeneous travellers

ABSTRACT

Autonomous vehicles (AV) can solve vehicle relocation problems faced by traditional one-way vehicle-sharing systems. This paper explores the deterministic time-dependent system optimum of mixed shared AVs (SAV) and human vehicles (SHV) system to provide the benchmark for the situation of mixed vehicle flows. In such a system, the system planner determines vehicle-traveller assignment and optimal vehicle routing in transportation networks to serve predetermined travel demand of heterogeneous travellers. Due to large number of vehicles involved, travel time is considered endogenous with congestion. Using link transmission model (LTM) as a traffic flow model, the deterministic time-dependent system optimum is formulated as linear programming (LP) model to minimize the comprehensive cost including travellers’ travel time cost, waiting time cost and empty vehicle repositioning time cost. Numerical examples are conducted to show system performances and model effectiveness.     

出行量预测不确定下基于灵敏度分析的拥挤收费定价模型

拥挤收费是改善城市交通的有效手段.对拥挤收费定价的研究方法之一,就是针对固定的出行量进行收费设计.由于出行量预测不确定的因素,应针对长期出行量预测不确定的情况,利用灵敏度分析的方法,对拥挤收费定价的问题进行研究.首先研究了出行者出行的广义费用,然后考虑出行者的出行决策及出行量预测不确定的因素,给出一个拥挤收费定价模型,为交通管理者提供理论依据.     

Fluid dynamics models and their applications in transportation and pricing

Fluid dynamics models provide a powerful deterministic technique to approximate stochasticity in a variety of application areas. In this paper, we study two classes of fluid models, investigate their relationship as well as some of their applications. This analysis allows us to provide analytical models of travel times as they arise in dynamically evolving environments, such as transportation networks as well as supply chains. In particular, using the laws of hydrodynamic theory, we first propose and examine a general second-order fluid model. We consider a first-order approximation of this model and show how it is helpful in analyzing the dynamic traffic equilibrium problem. Furthermore, we present an alternate class of fluid models that are traditionally used in the context of dynamic traffic assignment. By interpreting travel times as price/inventory–sojourn-time relationships, we are also able to connect this approach with a tractable fluid model in the context of dynamic pricing and inventory management.     

Modelling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems

Many research papers have presented mathematical models for vehicle scheduling. Several of these models have been embedded in commercial decision support systems for intra-city vehicle scheduling for launderies, grocery stores, banks, express mail customers, etc. Virtually all of these models ignore the important issue of time-dependent travel speeds for intra-city travel. Travel speeds (and times) in nearly all metropolitan areas change drastically during the day because of congestion in certain parts of the city road network. The assumption of constant (time-independent) travel speeds seriously affects the usefulness of these models. This is particularly true when time windows (earliest and latest stop time constraints) and other scheduling issues are important. This research proposes a parsimonious model for time-dependent travel speeds and several approaches for estimating the parameters for this model. An example is presented to illustrate the proposed modelling approach. The issue of developing algorithms to find near-optimal vehicle schedules with time-dependent travel speeds is also discussed. The modelling approach presented in this paper has been implemented in a commercial courier vehicle scheduling system and was judged to be ‘very useful’ by users in a number of different metropolitan areas in the United States.     

Modelling and optimization of average travel time for a metro line by simulation and response surface methodology

This research presents a modelling and solution approach based on discrete-event simulation and response surface methodology for dealing with average passenger travel time optimization problem inherent to the metro planning process. The objective is to find the headways optimizing passenger average travel time with a satisfactory rate of carriage fullness. Due to some physical constraints, traffic safety and legal requirements, vehicle speeds cannot be raised any further to decrease travel time. But travel time can be optimized by arranging headways (i.e. the time period between the departure times of two consecutive transportation vehicles) in a timetable. In the presented approach, simulation metamodels that best fit the data collected from the simulated experiments are constructed to describe the relationship between the responses (average travel time and rate of carriage fullness) and input factors (headways). Then, the Derringer–Suich multi-response optimization procedure is used to determine the optimal settings of the input factors that produce the minimum value of the average travel time by providing a proper rate of carriage fullness. This methodology is applied for a real metro line, and good quality solutions are obtained with reduced number of experiments that needed to provide sufficient information for statistically acceptable results.     

A study of travel time prediction using universal kriging

This study describes an approach for predicting travel time by kriging. The kriging method, which is a means of spatial prediction, is used as prediction measure for car travel time in an imaginary four-dimensional space. Each point in the space represents a single journey: the coordinates of a point are the coordinates of the origin and destination on a plane. The travel time can then be viewed as a function over this four-dimensional space. The prediction relies on the feature that nearby points (in the four-dimensional space) will have almost the same travel time. In this approach, it is not necessary to break down travel times from origin to destination into link travel times. The approach will also allow us to use information from “probe vehicles” for travel time prediction in the near future. The feasibility of this approach is demonstrated through a case study in London and its environs. The case study uses 200 observations for verification. The multiple correlation coefficient of estimated travel time and the verification data is 0.9045. The results indicate that 95% prediction limits are between ±10 minutes and ±30 minutes for travel between two arbitrary points. This prediction method is effective for urban districts with links having changeable travel time owing to congestion.     

交通拥堵与空气质量——来自汽车尾号限行的证据

由于空气的污染来源众多,交通拥堵是否加剧了空气质量的恶化,一般情况下很难界定和区分。本文利用一个特殊的工具变量——北京市工作日高峰时段汽车根据尾号限行,来分析和回答上述问题。由于受文化习惯影响,居民在挑选车牌号码时一般都不选4,因此包含数字4的车牌号很少。每当限行尾号为4和9的工作日,北京市的道路交通相比其他工作日会更拥堵,这为我们提供了一个识别交通拥堵的独特指标。通过使用双重差分模型排除了大量干扰因素后,我们对北京市35个空气质量监测站点PM2.5浓度逐时数据的分析发现,在限行尾号为4和9的工作日,高峰时段与非高峰时段的PM2.5浓度差异,比其他工作日的差异高出9.46%。交通拥堵显著降低了空气质量。