Multi-criteria route planning based on a driver’s preferences in multi-criteria route selection

In this study, some different approaches were designed, implemented, and evaluated to perform multi-criteria route planning by considering a driver’s preferences in multi-criteria route selection. At first, by using a designed neuro-fuzzy toolbox, the driver’s preferences in multi-criteria route selection such as the preferred criteria in route selection, the number of route-rating classes, and the routes with the same rate were received. Next, to learn the driver’s preferences in multi-criteria route selection and to classify any route based on these preferences, a methodology was proposed using a locally linear neuro-fuzzy model (LLNFM) trained with an incremental tree based learning algorithm. In this regard, the proposed LLNFM-based methodology reached better results for running-times, as well as root mean square error (RMSE) estimations in learning and testing processes of training/checking data-set in comparison with those of the proposed adaptive neuro-fuzzy inference system (ANFIS) based methodology. Finally, the trained LLNFM-based methodology was utilized to plan and predict a driver’s preferred routes by classifying Pareto-optimal routes obtained by running the modified invasive weed optimization (IWO) algorithm between an origin and a destination of a real urban transportation network based on the driver’s preferences in multi-criteria route selection.     

Direct versus terminal freight routing on a network with concave costs

This paper develops a procedure for deciding whether to route a shipment through an intermediate transportation terminal or route it directly to its destination. The procedure applies to networks with many origins (e.g. 2000) and few destinations (e.g. 20, or vice versa), where each origin is served by exactly one terminal. This decision is difficult because of economies-to-scale in transportation, which cause the cost of routing a shipment through a terminal to depend on the routes chosen for other shipments. The optimization procedure developed here finds the optimal routes graphically with a one-dimensional search, and is sufficiently efficient to be programmed on a hand calculator or personal computer. The procedure also provides insights as to the sensitivity of the optimal solution to changes in model parameters.     

A new algorithm for optimal signal control in congested networks

Optimization of traffic lights in a congested network is formulated as a linear programming problem. The formulation adapted here takes into account particular capacity constraints for road links and for intersections. A necessary prerequisite for the determination of optimal green times is that representative a-priori information about the origin-destination and route choice pattern inside the network is available. Because any particular control strategy temporarily alters the effective turning rates at intersections, an iterative procedure is proposed here which accomplishes convergence of optimal signal control and resulting O-D flows. The efficiency of this optimization procedure is demonstrated in a case study for a network with fifteen intersections.     

Spatial decision support system for hazardous material truck routing

Shipping hazardous material (hazmat) places the public at risk. People who live or work near roads commonly traveled by hazmat trucks endure the greatest risk. Careful selection of roads used for a hazmat shipment can reduce the population at risk. On the other hand, a least time route will often consist of urban interstate, thus placing many people in harms way. Route selection is therefore the process of resolving the conflict between population at risk and efficiency considerations. To assist in resolving this conflict, a working spatial decision support system (SDSS) called Hazmat Path is developed. The proposed hazmat routing SDSS overcomes three significant challenges, namely handling a realistic network, offering sophisticated route generating heuristics and functioning on a desktop personal computer. The paper discusses creative approaches to data manipulation, data and solution visualization, user interfaces, and optimization heuristics implemented in Hazmat Path to meet these challenges.     

枢纽机场航线网络优化研究

枢纽机场航线网络优化主要解决由于航线网络结构与功能定位不匹配而导致的机场连通性低、航线网络同质化竞争严重、运行效率低下的问题。通过改进引力模型对城市对间的客流量进行预测,以此为预测的客流量为依据之一,以提高机场连通性为目的,构建航线网络优化模型,并进行求解。实现提高枢纽机场连通性、构建符合功能定位的层级网络的目标。并以位于我国中部,具有"连接南北,贯穿东西"地理优势的西安咸阳国际机场为例进行分析。由于国际航线受客观因素较多,本文主要研究国内客运航线,国际及货运不在本文研究之列。     

Efficient Transit Schedule Design of timing points: A comparison of Ant Colony and Genetic Algorithms

This work defines Transit Schedule Design (TSD) as an optimization problem to construct the transit schedule with the decision variables of the location of timing points and the amount of slack time associated with each timing point. Two heuristic procedures, Ant Colony and Genetic Algorithms, are developed for constructing optimal schedules for a fixed bus route. The paper presents a comparison of the fundamental features of the two algorithms. They are then calibrated based on data generated from micro-simulation of a bus route in Melbourne, Australia, to give rise to (near) optimal schedule designs. The algorithms are compared in terms of their accuracy and efficiency in providing the minimum cost solution. Although both procedures prove the ability to find the optimal solution, the Ant Colony procedure demonstrates a higher efficiency by evaluating less schedule designs to arrive at a ‘good’ solution. Potential benefits of the developed algorithms in bus route planning are also discussed.     

An optimization method for sustainable traffic control in urban areas

The optimization of traffic signalization in urban areas is formulated as a problem of finding the cycle length, the green times and the offset of traffic signals that minimize an objective function of performance indices. Typical approaches to this optimization problem include the maximization of traffic throughput or the minimization of vehicles’ delays, number of stops, fuel consumption, etc. Dynamic Traffic Assignment (DTA) models are widely used for online and offline applications for efficient deployment of traffic control strategies and the evaluation of traffic management schemes and policies. We propose an optimization method for combining dynamic traffic assignment and network control by minimizing the risk of potential loss induced to travelers by exceeding their budgeted travel time as a result of deployed traffic signal settings, using the Conditional Value-at-Risk model. The proposed methodology can be easily implemented by researchers or practitioners to evaluate their alternative strategies and aid them to choose the alternative with less potential risk. The traffic signal optimization procedure is implemented in TRANSYT-7F and the dynamic propagation and route choice of vehicles is simulated with a mesoscopic dynamic traffic assignment tool (DTALite) with fixed temporal demand and network characteristics. The proposed approach is applied to a reference test network used by many researchers for verification purposes. Numerical experiments provide evidence of the advantages of this optimization method with respect to conventional optimization techniques. The overall benefit to the performance of the network is evaluated with a Conditional Value-at-Risk Analysis where the optimal solution is the one presenting the least risk for ‘guaranteed’ total travel times.     

河百高速公路长老至平坎段路线方案研究

河池至百色高速公路属于典型的山岭区公路,地形、地质条件复杂,桥隧比例大,路线走廊带选择对于控制工程规模、降低造价具有重要意义。文章介绍了该路长老至平坎段路线方案比选研究情况,以期为类似工程的路线设计工作提供借鉴。     

The time-dependent pollution-routing problem

The Time-Dependent Pollution-Routing Problem (TDPRP) consists of routing a fleet of vehicles in order to serve a set of customers and determining the speeds on each leg of the routes. The cost function includes emissions and driver costs, taking into account traffic congestion which, at peak periods, significantly restricts vehicle speeds and increases emissions. We describe an integer linear programming formulation of the TDPRP and provide illustrative examples to motivate the problem and give insights about the tradeoffs it involves. We also provide an analytical characterization of the optimal solutions for a single-arc version of the problem, identifying conditions under which it is optimal to wait idly at certain locations in order to avoid congestion and to reduce the cost of emissions. Building on these analytical results we describe a novel departure time and speed optimization algorithm for the cases when the route is fixed. Finally, using benchmark instances, we present results on the computational performance of the proposed formulation and on the speed optimization procedure.     

An AI-based approach for transit route system planning and design

We present an AI-based solution approach to the transit network design problem (TNDP). Past approaches fall into three categories: optimization formulations of idealized situations, heuristic approaches, or practical guidelines and ad hoc procedures reflecting the professional judgement and practical experience of transit planners. We discuss the sources of complexity of the TNDP as well as the shortcomings of the previous approaches. This discussion motivates the need for AI search techniques that implement the existing designer's knowledge and expertise to achieve better solutions efficiently. Then we propose a hybrid solution approach that incorporates the knowledge and expertise of transit network planners and implements efficient search techniques using AI tools, algorithmic procedures developed by others, and modules for tools implemented in conventional languages. The three major components of the solution approach are presented, namely, the lisp-implemented route generation design algorithm (RGA), the analysis procedure TRUST (Transit Route Analyst), and the route improvement algorithm (RIA). An example illustration is included.     

A simulation model of reliable schedule design for a fixed transit route

This paper describes a simulation model of schedule design for a fixed transit route adopting the holding control strategy. The model is capable of determining the locations of time points and the amount of slack time allocated to each time point by minimizing the total cost associated with the schedule. The optimization is carried out through a process, which combines a heuristic search, enumeration, and population ranking and selection techniques. Examples showing applications and potential savings of the proposed model are given. It is shown that the model can serve as a practical tool for designing reliable, economical as well as operational transit schedules.     

The allocation of buses in heavily utilized networks with overlapping routes

Many transit systems outside North America are characterized by networks with extensively overlapping routes and buses frequently operating at, or close to, capacity. This paper addresses the problem of allocating a fleet of buses between routes in this type of system; a problem that must be solved recurrently by transit planners. A formulation of the problem is developed which recognizes passenger route choice behavior, and seeks to minimize a function of passenger wait time and bus crowding subject to constraints on the number of buses available and the provision of enough capacity on each route to carry all passengers who would select it. An algorithm is developed based on the decomposition of the problem into base allocation and surplus allocation components. The base allocation identifies a feasible solution using an (approx.) minimum number of buses. The surplus allocation is illustrated for the simple objective of minimizing the maximum crowding level on any route. The bus allocation procedure developed in this paper has been applied to part of the Cairo bus system in a completely manual procedure, and is proposed to be the central element of a short-range bus service planning process for that city.     

Bi-level GA and GIS for Multi-objective TSP Route Planning

Abstract

Route planning is usually carried out to achieve a single objective such as to minimize transport cost, distance traveled or travel time. This article explores an approach to multi-objective route planning using a genetic algorithm (GA) and geographical information system (GIS) approach. The method is applied to the case of a tourist sight-seeing itinerary, where a route is planned by a tour operator to cover a set of places of interest within a given area. The route planning takes into account four criteria including travel time, vehicle operating cost, safety and surrounding scenic view quality. The multi-objective route planning in this paper can be viewed as an extension of the traditional traveling salesman problem (TSP) since a tourist needs to pass through a number of sight points. The four criteria are quantified using the spatial analytic functions of GIS and a generalized cost for each link is calculated. As different criteria play different roles in the route selection process, and the best order of the multiple points needs to be determined, a bi-level GA has been devised. The upper level aims to determine the weights of each criterion, while the lower level attempts to determine the best order of the sights to be visited based on the new generalized cost that is derived from the weights at the upper level. Both levels collaborate during the iterations and the route with the minimal generalized cost is thus determined. The above sight-seeing route planning methodology has been examined in a region within the central area of Singapore covering 19 places of interest.     

Routing and scheduling of RoRo ships with stowage constraints

Roll-on/Roll-off ships are used for international transport of vehicles and other rolling equipment. We consider the problem where a ship sails between two geographical regions, picking up cargo in the first and making deliveries to the second. Several variations are considered with optional cargoes, flexible cargo quantities, and ship stability restrictions. Decisions must be made regarding the route and schedule of the ship as well as the stowage of cargo onboard. The problem is modeled as a mixed integer program, which has been solved using Xpress. In addition, a tailor made heuristic procedure is built using components from tabu search and squeaky wheel optimization. Extensive computational results are presented, showing that the heuristic is able to handle realistically sized problem instances.     

Routing aspects of electric vehicle drivers and their effects on network performance

This study investigates the routing aspects of battery electric vehicle (BEV) drivers and their effects on the overall traffic network performance. BEVs have unique characteristics such as range limitation, long battery recharging time, and recuperation of energy lost during the deceleration phase if equipped with regenerative braking system (RBS). In addition, the energy consumption rate per unit distance traveled is lower at moderate speed than at higher speed. This raises two interesting questions: (i) whether these characteristics of BEVs will lead to different route selection compared to conventional internal combustion engine vehicles (ICEVs), and (ii) whether such route selection implications of BEVs will affect the network performance. With the increasing market penetration of BEVs, these questions are becoming more important. This study formulates a multi-class dynamic user equilibrium (MCDUE) model to determine the equilibrium flows for mixed traffic consisting of BEVs and ICEVs. A simulation-based solution procedure is proposed for the MCDUE model. In the MCDUE model, BEVs select routes to minimize the generalized cost which includes route travel time, energy related costs and range anxiety cost, and ICEVs to minimize route travel time. Results from numerical experiments illustrate that BEV drivers select routes with lower speed to conserve and recuperate battery energy while ICEV drivers select shortest travel time routes. They also illustrate that the differences in route choice behavior of BEV and ICEV drivers can synergistically lead to reduction in total travel time and the network performance towards system optimum under certain conditions.     

A statistical approach to the traveling salesman problem

A statistical approach is shown to be adaptable to the N-city traveling salesman problem by considering route distances to be random variables which are continuous and normally distributed. A solution to the shortest route distance and path can be approximated by utilizing a Monte Carlo simulation to obtain a representative sample of possible journeys. The approach involves recursive statistical inference which is used to select next-city visits leading to the most probable minimum route path. A statistical selection of the minimum route path is computationally efficient and computer run time increases in proportion to the square of the number of cities as opposed to an (N - 1)! increase for a deterministic approach. The accuracy of the statistical approach is directly proportional to the number of Monte Carlo simulations.     

Ridership estimation procedure for a transit corridor with new bus rapid transit service

Ridership estimation is a critical step in the planning of a new transit route or change in service. Very often, when a new transit route is introduced, the existing routes will be modified, vehicle capacities changed, or service headways adjusted. This has made ridership forecasts for the new, existing, and modified routes challenging. This paper proposes and demonstrates a procedure that forecasts the ridership of all transit routes along a corridor when a new bus rapid transit (BRT) service is introduced and existing regular bus services are adjusted. The procedure uses demographic data along the corridor, a recent origin–destination survey data, and new and existing transit service features as inputs. It consists of two stages of transit assignment. In the first stage, a transit assignment is performed with the existing transit demand on the proposed BRT and existing bus routes, so that adjustments to the existing bus services can be identified. This transit assignment is performed iteratively until there is no adjustment in transit services. In the second stage, the transit assignment is carried out with the new BRT and adjusted regular bus services, but incorporates a potential growth in ridership because of the new BRT service. The final outputs of the procedure are ridership for all routes and route segments, boarding and alighting volumes at all stops, and a stop‐by‐stop trip matrix. The proposed ridership estimation procedure is applicable to a new BRT route with and without competing regular bus routes and with BRT vehicles traveling in dedicated lanes or in mixed traffic. The application of the proposed procedure is demonstrated via a case study along the Alameda Corridor in El Paso, Texas. Copyright © 2015 John Wiley & Sons, Ltd.     

Connectivity-based optimization of vehicle route and speed for improved fuel economy

Traditionally, vehicle route planning problem focuses on route optimization based on traffic data and surrounding environment. This paper proposes a novel extended vehicle route planning problem, called vehicle macroscopic motion planning (VMMP) problem, to optimize vehicle route and speed simultaneously using both traffic data and vehicle characteristics to improve fuel economy for a given expected trip time. The required traffic data and neighbouring vehicle dynamic parameters can be collected through the vehicle connectivity (e.g. vehicle-to-vehicle, vehicle-to-infrastructure, vehicle-to-cloud, etc.) developed rapidly in recent years. A genetic algorithm based co-optimization method, along with an adaptive real-time optimization strategy, is proposed to solve the proposed VMMP problem. It is able to provide the fuel economic route and reference speed for drivers or automated vehicles to improve the vehicle fuel economy. A co-simulation model, combining a traffic model based on SUMO (Simulation of Urban MObility) with a Simulink powertrain model, is developed to validate the proposed VMMP method. Four simulation studies, based on a real traffic network, are conducted for validating the proposed VMMP: (1) ideal traffic environment without traffic light and jam for studying the fuel economy improvement, (2) traffic environment with traffic light for validating the proposed traffic light penalty model, (3) traffic environment with traffic light and jam for validating the proposed adaptive real-time optimization strategy, and (4) investigating the effect of different powertrain platforms to fuel economy using two different vehicle platforms. Simulation results show that the proposed VMMP method is able to improve vehicle fuel economy significantly. For instance, comparing with the fastest route, the fuel economy using the proposed VMMP method is improved by up to 15%.     

Optimal routing of a single vehicle with loading and unloading constraints

A real‐life situation in which a trucker has to collect a cargo of similar size from n different customers spread out in a given region and to deliver them to n locations spread out in another far‐away region has been formulated as a route‐design problem for a single vehicle. The minimal total time of loading, shipping and unloading is considered for different reshuffling methods, and the optimal method is determined. A solution procedure by enumeration is suggested to solve an actual small size problem, and an illustration is provided.     

Globally energy-optimal speed planning for road vehicles on a given route

This paper provides a globally optimal solution to an important problem: given a real-world route, what is the most energy-efficient way to drive a vehicle from the origin to the destination within a certain period of time. Along the route, there may be multiple stop signs, traffic lights, turns and curved segments, roads with different grades and speed limits, and even leading vehicles with pre-known speed profiles. Most of such route information and features are actually constraints to the optimal vehicle speed control problem, but these constraints are described in two different domains. The most important concept in solving this problem is to convert the distance-domain route constraints to some time-domain state and input constraints that can be handled by optimization methods such as dynamic programming (DP). Multiple techniques including cost-to-go function interpolation and parallel computing are used to reduce the computation of DP and make the problem solvable within a reasonable amount of time on a personal computer.