Pruning and ranking the Pareto optimal set,application for the dynamic multi‐objective network design problem

Solving the multi‐objective network design problem (MONDP) resorts to a Pareto optimal set. This set can provide additional information like trade‐offs between objectives for the decision making process, which is not available if the compensation principle would be chosen in advance. However, the Pareto optimal set of solutions can become large, especially if the objectives are mainly opposed. As a consequence, the Pareto optimal set may become difficult to analyze and to comprehend. In this case, pruning and ranking becomes attractive to reduce the Pareto optimal set and to rank the solutions to assist the decision maker. Because the method used, may influence the eventual decisions taken, it is important to choose a method that corresponds best with the underlying decision process and is in accordance with the qualities of the data used. We provided a review of some methods to prune and rank the Pareto optimal set to illustrate the advantages and disadvantages of these methods. The methods are applied using the outcome of solving the dynamic MONDP in which minimizing externalities of traffic are the objectives, and dynamic traffic management measures are the decision variables. For this, we solved the dynamic MONDP for a realistic network of the city Almelo in the Netherlands using the non‐dominated sorting genetic algorithm II. For ranking, we propose to use a fuzzy outranking method that can take uncertainties regarding the data quality and the perception of decision makers into account; and for pruning, a method that explicitly reckons with significant trade‐offs has been identified as the more suitable method to assist the decision making process. Copyright © 2012 John Wiley & Sons, Ltd.     

Distributed coordinated in-vehicle online routing using mixed-strategy congestion game

This study proposes a coordinated online in-vehicle routing mechanism for smart vehicles with real-time information exchange and portable computation capabilities. The proposed coordinated routing mechanism incorporates a discrete choice model to account for drivers’ behavior, and is implemented by a simultaneously-updating distributed algorithm. This study shows the existence of an equilibrium coordinated routing decision for the mixed-strategy routing game and the convergence of the distributed algorithm to the equilibrium routing decision, assuming individual smart vehicles are selfish players seeking to minimize their own travel time. Numerical experiments conducted based on Sioux Falls city network indicate that the proposed distributed algorithm converges quickly under different smart vehicle penetrations, thus it possesses a great potential for online applications. Moreover, the proposed coordinated routing mechanism outperforms traditional independent selfish-routing mechanism; it reduces travel time for both overall system and individual vehicles, which represents the core idea of Intelligent Transportation Systems (ITS).     

Validation of a schedule‐based capacity restraint transit assignment model for a large‐scale network

This paper describes the application of a capacity restraint trip assignment algorithm to a real, large‐scale transit network and the validation of the results. Unlike the conventional frequency‐based approach, the network formulation of the proposed model is dynamic and schedule‐based. Transit vehicles are assumed to operate to a set of pre‐determined schedules. Passengers are assumed to select paths based on a generalized cost function including in‐vehicle and out‐of‐vehicle time and line change penalty. The time‐varying passenger demand is loaded onto the network by a time increment simulation method, which ensures that the capacity restraint of each vehicle during passenger boarding is strictly observed. The optimal‐path and path‐loading algorithms are applied iteratively by the method of successive averages until the network converges to the predictive dynamic user equilibrium. The Hong Kong Mass Transit Railway network is used to validate the model results. The potential applications of the model are also discussed.     

A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

A time‐staged multi‐objective network‐design model

A multi‐objective, time‐staged network‐design problem is formulated. Through transformation, the problem is decomposed into a set of single‐period, single‐objective problems. Lexicographic ordering is instrumental in effecting this transformation; it also allows a backward‐recursion algorithm to be applied using strong pruning criteria. Furthermore, monotonicity properties enable us to solve the problem using the familiar tree‐search algorithms. The solution method has several desirable properties — as shown by an example and a case study of Tripoli Province, Libya. First, the algorithm ensures continuity of project implementation over the multi time‐periods and provides optimality in later computational stages irrespective of the decision at an interim stage. Second, the algorithm tends to provide accessibility to unconnected regions in the study area at low user‐cost without employing weights to the two objective functions of accessibility and user‐cost efficiency. Such a property is deemed advantageous for suggesting transportation investments based purely on purchasing the greatest benefit for each dollar, with political neutrality strictly maintained.     

Conflict‐free time‐based trajectory planning for aircraft taxi automation with refined taxiway modeling

To mitigate airport congestion caused by increasing air traffic demand, the trajectory‐based surface operations concept has been proposed to improve surface movement efficiency while maintaining safety. It utilizes decision support tools to provide optimized time‐based trajectories for each aircraft and uses automation systems to guide surface movements and monitor their conformance with assigned trajectories. Whether the time‐based trajectories can be effectively followed so that the expected benefits can be guaranteed depends firstly on whether these trajectories are realistic. So, this paper first deals with the modeling biases of the network model typically used for taxi trajectory planning via refined taxiway modeling. Then it presents a zone control‐based dynamic routing and timing algorithm upon the refined taxiway model to find the shortest time taxi route and timings for an aircraft. Finally, the presented algorithm is integrated with a sequential planning framework to continuously decide taxi routes and timings. Experimental results demonstrate that the solution time for an aircraft can be steadily around a few milliseconds with timely cleaning of expired time windows, showing potential for real‐time decision support applications. The results also show the advantages of the proposed methodology over existing approaches. Copyright © 2015 John Wiley & Sons, Ltd.     

Network equilibrium for congested multi‐mode networks with elastic demand

This paper proposes an elastic demand network equilibrium model for networks with transit and walking modes. In Hong Kong, the multi‐mode transit system services over 90% of the total journeys and the demand on it is continuously increasing. Transit and walking modes are related to each other as transit passengers have to walk to and from transit stops. In this paper, the multi‐mode elastic‐demand network equilibrium problem is formulated as a variational inequality problem where the combined mode and route choices are modeled in a hierarchical logit structures and the total travel demand for each origin‐destination pair is explicitly given by an elastic demand function. In addition, the capacity constraint for transit vehicles and the effects of bi‐directional flows on walkways are considered in the proposed model. All these congestion effects are taken into account for modeling the travel choices. A solution algorithm is developed to solve the multi‐mode elastic‐demand network equilibrium model. It is based on a Block Gauss‐Seidel decomposition approach coupled with the method of successive averages. A numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Orchestration of driving simulator scenarios based on dynamic actor preparation and automated action planning

In driving simulation, a scenario includes definitions of the road environment, the traffic situation, simulated vehicles’ interactions with the participant’s vehicle and measurements that need to be collected. The scenarios need to be designed in such a way that the research questions to be studied can be answered, which commonly imply exposing the participant for a couple of predefined specific situations that has to be both realistic and repeatable. This article presents an integrated algorithm based on Dynamic Actor Preparation and Automated Action Planning to control autonomous simulated vehicles in the simulation in order to generate predefined situations. This algorithm is thus able to plan driving actions for autonomous vehicles based on specific tasks with relevant contextual information as well as handling longitudinal transportation of simulated vehicles based on the contextual information in an automated manner. The conducted experiment shows that the algorithm is able to guarantee repeatability under autonomous traffic flow. The presented algorithm can benefit not only the driving simulation community, but also relevant areas, such as autonomous vehicle and in-vehicle device design by providing them with an algorithm for target pursue and driving task accomplishment, which can be used to design a human-vehicle cooperation system in the coming era of autonomous driving.     

A decision support approach to the computerisation of some operational decision problems in community transport

Community Transport (CT) in the UK operates a diverse range of services, and organisations are computerising management and operational functions. This paper describes the approach which has been taken to computerising four operational decision making functions.

The paper considers models of human decision making and problem solving, with particular reference to an information processing view of cognitive activity and to perception and memory. The design of decision support systems is also discussed.

Four decision problems are considered. For each, the paper considers how people tackle the problem, how computers can be used to tackle it and the approach which has been adopted.

For allocating trips to vehicles using a diary, the approach has been to provide a representation on screen of a manual diary. For vehicle brokerage, vehicles are presented to the operator allocating a booking in an order based on the Sequence Number, an index of how ‘difficult to book’ a vehicle is, and the distance of the vehicle's base from the start point of the trip. For the sorting of passenger pick‐ups into an efficient tour, traditional solutions to the travelling salesperson problem have been rejected in favour of a solution using spacefilling curves. Finally, for allocating dial‐a‐ride passenger trips to vehicle shifts an approach has been chosen which presents the operator with appropriate information rather than attempting to automate the scheduling.

The paper concludes that the approach to the diary has been successful and accepted by operators, although the similar approach to the dial‐a‐ride scheduling has not, as the system has not yet been able to replace manual scheduling aids. The facility to order passenger pick‐ups is little used by operators. Finally, it is suggested that the vehicle brokerage problem may be an appropriate use of fuzzy logic.     

Cooperative GNSS positioning aided by road-features measurements

Cooperation between road users through V2X communication is a way to improve GNSS localization accuracy. When vehicles localization systems involve standalone GNSS receivers, the resulting accuracy can be affected by satellite-specific errors of several meters. This paper studies how road-features like lane marking detected by on-board cameras can be exploited to reduce absolute position errors of cooperative vehicles sharing information in real-time in a network. The algorithms considered in this work are based on a error bounded set membership strategy. In every vehicle, a set membership algorithm computes the absolute position and an estimation of the satellite-specific errors by using raw GNSS pseudoranges, lane boundary measurements and a 2D georeferenced road map which provides absolute geometric constraints. As lane-boundary measurements provide essentially cross-track corrections in the position estimation process, cooperation enables the vehicles to improve their own estimates thanks to the different orientation of the roads. Set-membership methods are very efficient to solve this problem since they do not involve any independence hypothesis of the errors and so, the same information can be used several times in the computation. Such class of algorithm provides a novel approach to improve position accuracy for connected vehicles guaranteeing the integrity of the computed solution which is pivoting for automated automotive systems requiring guaranteed safety-critical solutions. Results from simulations and real experiments show that sharing position corrections reduces significantly satellite-specific GNSS errors effects in both cross-track and along-track components. Moreover, it is shown that lane-boundary measurements help reducing estimation errors for all the networked vehicles even those which are not equipped with an embedded perception system.     

Coordinated platooning with multiple speeds

In a platoon, vehicles travel one after another with small intervehicle distances; trailing vehicles in a platoon save fuel because they experience less aerodynamic drag. This work presents a coordinated platooning model with multiple speed options that integrates scheduling, routing, speed selection, and platoon formation/dissolution in a mixed-integer linear program that minimizes the total fuel consumed by a set of vehicles while traveling between their respective origins and destinations. The performance of this model is numerically tested on a grid network and the Chicago-area highway network. We find that the fuel-savings factor of a multivehicle system significantly depends on the time each vehicle is allowed to stay in the network; this time affects vehicles’ available speed choices, possible routes, and the amount of time for coordinating platoon formation. For problem instances with a large number of vehicles, we propose and test a heuristic decomposed approach that applies a clustering algorithm to partition the set of vehicles and then routes each group separately. When the set of vehicles is large and the available computational time is small, the decomposed approach finds significantly better solutions than does the full model.     

Truck capacity analysis in a cross‐dock transportation network considering direct shipment

In a transportation network, decision making parameters may change and may cause the optimum value of objective function to vary in a specific range. Therefore, managers try to identify the effects of these changes by sensitive analysis to find appropriate solutions. In this paper, first, a model for cross‐dock transportation network considering direct shipment is presented, and then an algorithm based on branch and bound algorithm and dual price concept for sensitive analysis is developed. When managers encounter problems such as budget limit, they may decide to change the capacity of trucks as a procedure to reduce the transportation costs of the network. The algorithm provides a useful lower bound on the solutions of the problems and makes it easy for the managers to eliminate inappropriate options of truck capacities, which cannot lead to cost reduction. To verify the algorithm, an example will be given at the end of the paper. Copyright © 2013 John Wiley & Sons, Ltd.     

An operational planning model for the dynamic vehicle allocation problem with uncertain demands

The dynamic vehicle allocation problem arises when a motor carrier must simultaneously and in real time coordinate the dispatching of vehicles from one region to the next all over the country. The decision to send a vehicle loaded or empty from one region to the next, arriving in the destination region at some point in the future, must anticipate the downstream impacts of the decision. The consequences of another load in a particular region at some point in the future, however, are highly uncertain. A simple methodology is proposed which calculates approximately the marginal value of an additional vehicle in each region in the future. This information is then used to generate a standard pure network which can be efficiently optimized to give dispatching decisions for today.     

A bi‐level programming approach — Optimal transit fare under line capacity constraints

The fare of a transit line is one of the important decision variables for transit network design. It has been advocated as an efficient means of coordinating the transit passenger flows and of alleviating congestion in the transit network. This paper shows how transit fare can be optimized so as to balance the passenger flow on the transit network and to reduce the overload delays of passengers at transit stops. A bi‐level programming method is developed to optimize the transit fare under line capacity constraints. The upper‐level problem seeks to minimize the total network travel time, while the lower‐level problem is a stochastic user equilibrium transit assignment model with line capacity constraints. A heuristic solution algorithm based on sensitivity analysis is proposed. Numerical example is used to illustrate the application of the proposed model and solution algorithm.     

Guaranteed prediction and estimation of the state of a road network

The paper presents an algorithm for the prediction and estimation of the state of a road network comprising freeways and arterials, described by a Cell Transmission Model (CTM). CTM divides the network into a collection of links. Each link is characterized by its fundamental diagram, which relates link speed to link density. The state of the network is the vector of link densities. The state is observed through measurements of speed and flow on some links. Demand is specified by the volume of vehicles entering the network at some links, and by split ratios according to which vehicles are routed through the network. There is model uncertainty: the parameters of the fundamental diagram are uncertain. There is uncertainty in the demand around the nominal forecast. Lastly, the measurements are uncertain. The uncertainty in each model parameter, demand, and measurement is specified by an interval. Given measurements over a time interval [0, t] and a horizon τ ? 0, the algorithm computes a set of states with the guarantee that the actual state at time (t + τ) will lie in this set, consistent with the given measurements. In standard terminology the algorithm is a state prediction or an estimate accordingly as τ > 0 or =0. The flow exiting a link may be controlled by an open- or closed-loop controller such as a signal or ramp meter. An open-loop controller does not change the algorithm, indeed it may make the system more predictable by tightening density bounds downstream of the controller. In the feedback case, the value of the control depends on the estimated state bounds, and the algorithm is extended to compute the range of possible closed-loop control values. The algorithm is used in a proposed design of a decision support system for the I-80 integrated corridor.     

Solving the Median Shortest Path Problem in the Planning and Design of Urban Transportation Networks Using a Vector Labeling Algorithm

This paper proposes an alternative algorithm to solve the median shortest path problem (MSPP) in the planning and design of urban transportation networks. The proposed vector labeling algorithm is based on the labeling of each node in terms of a multiple and conflicting vector of objectives which deletes cyclic, infeasible and extreme-dominated paths in the criteria space imposing cyclic break (CB), path cost constraint (PCC) and access cost parameter (ACP) respectively. The output of the algorithm is a set of Pareto optimal paths (POP) with an objective vector from predetermined origin to destination nodes. Thus, this paper formulates an algorithm to identify a non-inferior solution set of POP based on a non-dominated set of objective vectors that leaves the ultimate decision to decision-makers. A numerical experiment is conducted using an artificial transportation network in order to validate and compare results. Sensitivity analysis has shown that the proposed algorithm is more efficient and advantageous over existing solutions in terms of computing execution time and memory space used.     

Stochastic eco-routing in a signalized traffic network

In this paper, an eco-routing algorithm is developed for vehicles in a signalized traffic network. The proposed method incorporates a microscopic vehicle emission model into a Markov decision process (MDP). Instead of using GPS-based vehicle trajectory data, which are used by many existing eco-routing algorithm, high resolution traffic data including vehicle arrival and signal status information are used as primary inputs. The proposed method can work with any microscopic vehicle model that uses vehicle trajectories as inputs and gives related emission rates as outputs. Furthermore, a constrained eco-routing problem is proposed to deal with the situation where multiple costs present. This is done by transferring the original MDP based formulation to a linear programming formulation. Besides the primary cost, additional costs are considered as constraints. Two numerical examples are given using the field data obtained from City of Pasadena, California, USA. The eco-routing algorithm for single objective is compared against the traditional shortest path algorithm, Dijkstra’s algorithm. Average reductions of CO emission around 20% are observed.     

Microscopic modeling of large‐scale pedestrian–vehicle conflicts in the city of Madinah,Saudi Arabia

This paper presents a micro‐simulation modeling framework for evaluating pedestrian–vehicle conflicts in crowded crossing areas. The framework adopts a simulation approach that models vehicles and pedestrians at the microscopic level while satisfying two sets of constraints: (1) flow constraints and (2) non‐collision constraints. Pedestrians move across two‐directional cells as opposed to one‐dimensional lanes as in the case of vehicles; therefore, extra caution is considered when modeling the shared space between vehicles and pedestrians. The framework is used to assess large‐scale pedestrian–vehicle conflicts in a highly congested ring road in the City of Madinah that carries 20 000 vehicles/hour and crossed by 140 000 pedestrians/hour after a major congregational prayer. The quantitative and visual results of the simulation exhibits serious conflicts between pedestrians and vehicles, resulting in considerable delays for pedestrians crossing the road (9 minutes average delay) and slow traffic conditions (average speed <10 km/hour). The model is then used to evaluate the following three mitigating strategies: (1) pedestrian‐only phase; (2) grade separation; and (3) pedestrian mall. A matrix of operational measures of effectiveness for network‐wide performance (e.g., average travel time, average speed) and for pedestrian‐specific performance (e.g., mean speed, mean density, mean delay, mean moving time) is used to assess the effectiveness of the proposed strategies. Copyright © 2012 John Wiley & Sons, Ltd.     

A network enhancement model with integrated lane reorganization and traffic control strategies

Lane reorganization strategies such as lane reversal, one‐way street, turning restriction, and cross elimination have demonstrated their effectiveness in enhancing transportation network capacity. However, how to select the most appropriate combination of those strategies in a network remains challenging to transportation professionals considering the complex interactions among those strategies and their impacts on conventional traffic control components. This article contributes to developing a mathematical model for a traffic equilibrium network, in which optimization of lane reorganization and traffic control strategies are integrated in a unified framework. The model features a bi‐level structure with the upper‐level model describing the decision of the transportation authorities for maximizing the network capacity. A variational inequality (VI) formulation of the user equilibrium (UE) behavior in choosing routes in response to various strategies is developed in the lower level. A genetic algorithm (GA) based heuristic is used to yield meta‐optimal solutions to the model. Results from extensive numerical analyses reveal the promising property of the proposed model in enhancing network capacity and reducing congestion. Copyright © 2016 John Wiley & Sons, Ltd.     

Synchronized Production and Transportation Planning Using Subcontracted Vehicles in a Production-Distribution Network

Abstract

Effective management of interfaces between procurement, supply, production and distribution for higher efficiency in the supply chain is an important issue in global manufacturing, where the synchronization of production and transportation planning represents important savings in operational costs. This paper focuses on the synchronization of production planning and transportation planning in a production distribution network, where transportation is subcontracted to a professional transportation enterprise (PTE) for vehicle-hiring. Dynamic and flexible numbers of vehicles are used to cater for fast changing market demands. Thus, the number of vehicles to be hired is viewed from the planning point of view as an operational decision considered simultaneously with production and transportation planning. A mathematical model – SPTP/MTDS – for synchronized production and transportation planning under multiple times and direct shipping strategy (MTDS) is discussed, and a Lagrange relaxation decomposition-based two layer decision procedure (LRD-TLDP) is developed. By introducing artificial decision variables and Lagrange multipliers, SPTP/MTDS is decomposed into a production decision sub-problem (SPTP-PD), and a distribution decision sub-problem (SPTP-DD). A priority-based assignment heuristic and a partial chain-based genetic algorithm are developed to solve SPTP-PD and SPTP-DD, respectively. An illustration of the application of the model in an electronic appliance manufacturing enterprise in China is presented.