Optimal hierarchical system of a grid road network

This paper develops a simple analytical model for determining the hierarchical system of road networks. The model is based on a grid road network where roads are classified into three types according to road widths and travel speeds. We derive the optimal ratios of road areas that minimize the average and maximum travel time. Minimizing the average travel time provides an efficient solution, whereas minimizing the maximum travel time provides an equitable solution. Both of the solutions are expressed in terms of road widths and travel speeds. As an application of the grid network model, we evaluate the hierarchical system of the road network of Tokyo.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

The traffic problem: Modeling of the overtaking

The classical microscopic single line follow‐the‐leader model of a road traffic may collapse in finite time due to a car collision. In order to avoid the collision, the natural action of a driver would be to overtake the slower car. We propose a simple model of overtaking assuming a circular road. The model is a dynamical system with discontinuous right‐hand side (the Filippov system). As a case study, we assumed that the system consists of N =3 identical cars. We studied a particular periodic solution (oscillatory pattern). We explored the possibility to use the standard software (AUTO97) to continue the pattern with respect to a parameter. Copyright © 2009 John Wiley & Sons, Ltd.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies

This study investigates the effectiveness of simultaneous and staged evacuation strategies using agent-based simulation. In the simultaneous strategy, all residents are informed to evacuate simultaneously, whereas in the staged evacuation strategy, residents in different zones are organized to evacuate in an order based on different sequences of the zones within the affected area. This study uses an agent-based technique to model traffic flows at the level of individual vehicles and investigates the collective behaviours of evacuating vehicles. We conducted simulations using a microscopic simulation system called Paramics on three types of road network structures under different population densities. The three types of road network structures include a grid road structure, a ring road structure, and a real road structure from the City of San Marcos, Texas. Default rules in Paramics were used for trip generation, destination choice, and route choice. Simulation results indicate that (1) there is no evacuation strategy that can be considered as the best strategy across different road network structures, and the performance of the strategies depends on both road network structure and population density; (2) if the population density in the affected area is high and the underlying road network structure is a grid structure, then a staged evacuation strategy that alternates non-adjacent zones in the affected area is effective in reducing the overall evacuation time.     

The sector design and assignment problem for snow disposal operations

Winter road maintenance operations involve a host of decision-making problems at the strategic, tactical, operational, and real-time levels. Those operations include spreading of chemicals and abrasives, snow plowing, loading snow into trucks, and hauling snow to disposal sites. In this paper, we present a model and two heuristic solution approaches based on mathematical optimization for the problem of partitioning a road network into sectors and allocating sectors to snow disposal sites for snow disposal operations. Given a road network and a set of planned disposal sites, the problem is to determine a set of non-overlapping subnetworks, called sectors, according to several criteria related to the operational effectiveness and the geographical layout, and to assign each sector to a single snow disposal site so as to respect the capacities of the disposal sites, while minimizing relevant variable and fixed costs. Our approach uses single street segments as the units of analysis and we consider sector contiguity, sector balance and sector shape constraints, hourly and annual disposal site capacities, as well as single assignment requirements. The resulting model is based on a multi-commodity network flow structure to impose the contiguity constraints in a linear form. The two solution approaches were tested on data from the city of Montreal in Canada.     

An N-path user equilibrium for transportation networks

The traditional trip-based approach to transportation modeling has been employed for the past decade. The last step of the trip-based modeling approach is traffic assignment, which has been typically formulated as a user equilibrium (UE) problem. In the conventional perspective, the definition of UE traffic assignment is the condition that no road user can unilaterally change routes to reduce their travel time. An equivalent definition is that the travel times of all the used paths between any given origin–destination pair are equal and less than those of the unused paths. The underlying assumption of the UE definition is that road users have full information on the available transportation paths and can potentially use any path if the currently used path is overly congested. However, a more practical scenario is that each road user has a limited path set within which she/he can choose routes from. In this new scenario, we call the resulting user equilibrium an N-path user equilibrium (NPUE), in which each road user has only N paths to select from when making route choices in the network. We introduce a new formulation of the NPUE and derive optimality conditions based on this formulation. Different from traditional modeling framework, the constraints of the proposed model are of linear form, which makes it possible to solve the problem with conventional convex programming techniques. We also show that the traditional UE is a special case of an NPUE and prove the uniqueness of the resulting flow pattern of the NPUE. To efficiently solve this problem, we devise path-based and link-based solution algorithms. The proposed solution algorithms are empirically applied to networks of various sizes to examine the impact of constrained user path sets. Numerical results demonstrate that NPUE results can differ significantly from UE results depending on the number of paths available to road users. In addition, we observed an interesting phenomenon, where increasing the number of paths available to road users can sometimes decrease the overall system performance due to their selfish routing behaviors. This paradox demonstrates that network information should be provided with caution, as such information can do more harm than good in certain transportation systems.     

Optimization Models for Forest Road Upgrade Planning

Road blocking due to thawing or heavy rains annually contribute to a considerable loss in Swedish forestry. Companies are forced to build up large stocks of raw material (saw and pulp logs) in order to secure a continuous supply when access to the road network is uncertain. Storage outdoors leads to quality deterioration and monetary losses. Other related costs due to road blocking are road damage and longer haulage distances. One approach to reduce the losses due to road blocks is to upgrade the road network to a standard that guarantees accessibility. We consider the road upgrade problem from the perspective of Swedish forest companies with a planning horizon of about one decade. The objective is to minimize the combined upgrade and transportation costs. We present two mixed integer programming models, which are uncapacitated fixed charge network flow problems including multiple assortments, several time periods and a set of road classes. One model is based on arc flows and one on route flows. For a typical planning instance, the models become large and we propose how to improve solution performance through model strengthening. The models are tested in a case study for a major Swedish forest company.      

District design for arc-routing applications

In this paper we address the problem of district design for the organisation of arc-routing activities. In particular, the focus is on operations like winter gritting and road maintenance. The problem involves how to allocate the road network edges to a set of depots with given locations. The collection of edges assigned to a facility forms a district in which routes have to be designed that start and end at the facility. Apart from the ability to support good arc routing, well-designed districts for road-maintenance operations should have the road network to be serviced connected and should define clear geographical boundaries. We present three districting heuristics and evaluate the quality of the partitions by solving capacitated arc routing problems in the districts, and by comparing the solution values with a multi-depot CARP cutting plane lower bound. Our experiments reveal that based on global information about the distribution system (ie the number of facilities or districts, the average edge demand and the vehicle capacity) and by using simple guidelines, an adequate districting policy may be selected.     

A general model of road traffic accidents

A general model that relates road traffic accidents to the number of vehicles involved, and the number of primary causes of such accidents, is presented. The model considers traffic accidents as failures of a road traffic network system to meet social and economic constraints, and therefore as a measure of the unreliability of such a system. The equations apply to accidents in the real time domain as well as to mean values per unit of vehicle exposure time or vehicle distance. They also apply to single vehicles and drivers, groups of drivers and fleets of vehicles, and the entire vehicle and driving population. They can be used for sections of a network or for a whole network.The equations used have a large number of terms, hence bias errors are common in road accident investigations.     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.     

Hubbing and routing in postal delivery systems

We consider the combined hubbing and routing problem in postal delivery systems and develop an iterative two-stage solution procedure for the problem. In the first stage, hub locations are determined and postal offices are multiply allocated to the hubs. The second stage gives the routes in hub regions that alter the distances between points used in the hub-location problem. The procedure then iterates between two stages by updating the distances used in hubbing in order to produce a route-compatible hub configuration. Computational experience is reported for the test problems taken from the literature. For a case study Turkish postal delivery system data are utilized. As the case study is applied on a road network, a final stage, seeking improvements based on special structures in the routed network, is appended to the two-stage solution procedure.     

基于改进蚁群算法的最短路径问题研究及应用

蚁群系统作为一种蚁群算法是解决最短路径问题的一种行之有效的方法.然而,它自身也存在着一些缺陷,主要针对基本蚁群算法易陷入局部最优这一缺陷对其进行改进,集中体现在初始信息素求解和信息素更新这两方面.为了进一步了解改进蚁群算法的优点,进行了实验仿真:将改进的蚁群算法应用子模拟医疗救护GIS中,利用GIS的网络分析功能对城市道路网络的最短路径选择算法进行了深入地探讨研究,并以山西省太原市的交通路线作为实例进行研究.计算机仿真结果表明,改进的蚁群算法在解决最短路径问题时较基本蚁群算法的性能好,它具有一定的理论参考价值和现实意义.     

The periodic capacitated arc routing problem with irregular services

The aim of this paper is to introduce the periodic capacitated arc routing problem with irregular services. Some applications can be found in road maintenance operations and road network surveillance. The problem consists of determining a set of routes to cover a given network over a time horizon. The roads must be serviced a number of times in sub-periods over the time horizon, according to a hierarchy of arc classes. We present a mathematical model and a heuristic solution approach.     

Analytical existence of solutions to a system of nonlinear equations with application

We study the existence of analytical solutions to a system of nonlinear equations under constraints linked to the analysis of a road safety measure without computing second derivatives. We formally demonstrate this existence of solutions by applying a matrix inversion principle through Schur complement to a subsystem of equations derived from the main system. The analytical results thus obtained are used to construct a simple iterative procedure to look for optimal solutions as well as an initial solution adapted to data of each case study. We illustrate our results with simulated accident data obtained from the setting-up of a road safety measure. The numerical solutions thus obtained are then compared to those given through a classic Newton-Raphson type approach directly applied to the main system.     

Applying the flow-capturing location-allocation model to an authentic network: Edmonton, Canada

Traditional location-allocation models aim to locate network facilities to optimally serve demand expressed as weights at nodes. For some types of facilities demand is not expressed at nodes, but as passing network traffic. The flow-capturing location-allocation model responds to this type of demand and seeks to maximize one-time exposure of such traffic to facilities. This new model has previously been investigated only with small and contrived problems. In this paper, we apply the flow-capturing location-allocation model to morning-peak traffic in Edmonton, Canada. We explore the effectiveness of exact, vertex substitution, and greedy solution procedures; the first two are computationally demanding, the greedy is very efficient and extremely robust. We hypothesize that the greedy algorithm's robustness is enhanced by the structured flow present in an authentic urban road network. The flow-capturing model was derived to overcome flow cannibalization, wasteful redundant flow-capturing; we demonstrate that this is an important consideration in an authentic network. We conclude that real-world testing is an important aspect of location model development.     

Measure-valued solutions to nonlocal transport equations on networks

Aiming to describe traffic flow on road networks with long-range driver interactions, we study a nonlinear transport equation defined on an oriented network where the velocity field depends not only on the state variable but also on the distribution of the population. We prove existence, uniqueness and continuous dependence results of the solution intended in a suitable measure-theoretic sense. We also provide a representation formula in terms of the push-forward of the initial and boundary data along the network and discuss an explicit example of nonlocal velocity field fitting our framework.     

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

Car path tracking in traffic flow networks with bounded buffers at junctions

This article deals with the modeling for an individual car path through a road network, where the dynamics is driven by a coupled system of ordinary and partial differential equations. The network is characterized by bounded buffers at junctions that allow for the interpretation of roundabouts or on-ramps while the traffic dynamics is based on first-order macroscopic equations of Lighthill-Whitham-Richards (LWR) type. Trajectories for single drivers are then influenced by the surrounding traffic and can be tracked by appropriate numerical algorithms. The computational experiments show how the modeling framework can be used as navigation device.     

基于BP神经网络的道路交通事故预测

道路交通事故预测是交通研究的一个重要课题.以我国交通安全状况为研究对象,依据我国道路交通事故的特点,利用神经网络具有自学习、自组织、自适应能力特性,运用神经网络的方法及我国多个年度道路交通事故统计数据,建立了道路交通事故神经网络宏观预测模型,预测精度符合道路交通事故预测的要求.