Application of multiple criteria decision making for network improvement

In this paper we propose application of multiple criteria decision making to problems of a metropolitan network improvement plan. Initially, a bilevel multiple objective network design model is considered in two objectives which are minimal government budget and minimal total travel time of road users. We seek feasible improvement alternatives among those bottleneck links in an existing road network structure and travel demand. We present an effective heuristic algorithm to obtain noninferior solutions; then ELECTRE III multiple criteria decision making and group decision making are used to evaluate and to select a compromise solution among those noninferior solutions. From the design phase in multiple criteria decision making, multiple objective mathematical programming is used to formulate a continuous network design model. However, from the phase of evaluation, multiple criteria decision making to solve the discrete network design problem. The network of metropolitan Taipei is taken as an example to illustrate the operation of this model.     

The multi-objective network design problem using minimizing externalities as objectives: comparison of a genetic algorithm and simulated annealing framework

Incorporation of externalities in the Multi-Objective Network Design Problem (MO NDP) as objectives is an important step in designing sustainable networks. In this research the problem is defined as a bi-level optimization problem in which minimizing externalities are the objectives and link types which are associated with certain link characteristics are the discrete decision variables. Two distinct solution approaches for this multi-objective optimization problem are compared. The first heuristic is the non-dominated sorting genetic algorithm II (NSGA-II) and the second heuristic is the dominance based multi objective simulated annealing (DBMO-SA). Both heuristics have been applied on a small hypothetical test network as well as a realistic case of the city of Almelo in the Netherlands. The results show that both heuristics are capable of solving the MO NDP. However, the NSGA-II outperforms DBMO-SA, because it is more efficient in finding more non-dominated optimal solutions within the same computation time and maximum number of assessed solutions.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

Application of Ant System to network design problem

Network design problem (NDP) is the problem of choosing from among a set of alternative projects which optimizes an objective (e.g., minimizes total travel time), while keeping consumption of resources (e.g., budget) within their limits. This problem is difficult to solve, because of its combinatorial nature and nonconvexity of the objective function. Many algorithms are presented to solve the problem more efficiently, while trading-off accuracy with computational speed. This increase in speed stems from certain approximations in the formulation of the problem, decomposition, or heuristics. This study adapts a meta – heuristic approach to solve NDP, namely Ant System (AS). The algorithm is first designed, and then calibrated to solve NDP for the Sioux Falls test network. The behavior of the algorithm is then investigated. The result seems encouraging.     

Combinatorial programming,statistical optimization and the optimal transportation network problem

This paper presents and evaluates a branch and bound algorithm and two heuristic hill-climbing techniques to solve a discrete formulation of the optimal transportation network design problem. For practical applications it is proposed to combine a hill-climbing algorithm with a uniform random generation of the initial solutions, thereby inducing a statistical distribution of local optima. In order to determine when to stop sampling local optima and in order to provide an estimate of the exact optimum based on the whole distribution of local optima, we follow previous work and fit a Weibull distribution to the empirical distribution of local optima. Several extensions are made over previous work: in particular, a new confidence interval and a new stopping rule are proposed. The numerical application of the statistical optimization methodology to the network design algorithms consolidates the empirical validity of fitting a Weibull distribution to the empirical distribution of local optima. Numerical experiments with hill-climbing techniques of varying power suggest that the method is best applied with heuristics of intermediate quality: such heuristics provide many distinct sample points for statistical estimation while keeping the confidence intervals sufficiently narrow.     

A hybrid heuristic strategy for liquefied natural gas inventory routing

As liquefied natural gas (LNG) steadily grows to be a common mode for commercializing natural gas, LNG supply chain optimization is becoming a key technology for gas companies to maintain competitiveness. This paper develops methods for improving the solutions for a previously stated form of an LNG inventory routing problem (LNG-IRP). Motivated by the poor performance of a Dantzig-Wolfe-based decomposition approach for exact solutions, we develop a suite of advanced heuristic techniques and propose a hybrid heuristic strategy aiming to achieve improved solutions in shorter computational time. The heuristics include two phases: the advanced construction phase is based on a rolling time algorithm and a greedy randomized adaptive search procedure (GRASP); and the solution improvement phase is a series of novel MIP-based neighborhood search techniques. The proposed algorithms are evaluated based on a set of realistic large-scale instances seen in recent literature. Extensive computational results indicate that the hybrid heuristic strategy is able to obtain optimal or near optimal feasible solutions substantially faster than commercial optimization software and also the previously proposed heuristic methods.     

Transit-network design methodology for actual-size road networks

The main purpose of this study is to design a transit network of routes for handling actual-size road networks. This transit-network design problem is known to be complex and cumbersome. Thus, a heuristic methodology is proposed, taking into account the major concerns of transit authorities such as budget constraints, level-of-service standards and the attractiveness of the transit routes. In addition, this approach considers other important aspects of the problem including categorization of stops, multiclass of transit vehicles, hierarchy planning, system capacity (which has been largely ignored in past studies) and the integration between route-design and frequency-setting analyses. The process developed starts with the construction of a set of potential stops using a clustering concept. Then, by the use of Newton gravity theory and a special shortest-path procedure, a set of candidate routes is formed, categorized by hierarchy (mass, feeder, local routes). In the last step of the process a metaheuristic search engine is launched over the candidate routes, incorporating budgetary constraints, until a good solution is found. The algorithm was tested on the actual-size transit network of the city of Winnipeg; the results show that under the same conditions (budget and constraints) the proposed set of routes resulted in a reduction of 14% of total travel time compared to the existing transit network. In addition the methodology developed is compared favorably with other studies using the transit network of Mandl benchmark. The generality of the methodology was tested on the recent real dataset (pertaining to the year 2010) of the larger city of Chicago, in which a more efficient and optimized scheme was proposed for the existing rail system.     

The structure of the solution set to network optimisation problems

This paper argues that both heuristic and non-heuristic algorithms for the road network optimisation problem would benefit from a greater understanding of the structure of the set of feasible solutions to such problems. In order to provide this, a comparative study of a number of spatial combinatorial problems was undertaken. The results show that the road network optimisation problem is rich in good sub-optimal solutions. The implications of this finding for the development of optimising and heuristic algorithms are discussed, and some suggestions made as to where future research on network optimisation problems could most fruitfully be directed.     

The vehicle platooning problem: Computational complexity and heuristics

We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1–2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks.     

The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions

The tractor and semitrailer routing problem with many-to-many demand (TSRP-MMD) is investigated in this study. The TSRP-MMD extends the existing studies on the rollon–rolloff vehicle routing problem (RRVRP) to a many-to-many problem with an intercity line-haul network background. To demonstrate and utilize the energy efficiency of the tractor and semitrailer combination, the TSRP-MMD takes carbon dioxide (CO₂) emissions per ton-kilometer as the objective. Because the problem is NP-hard, a modified Clarke and Wright Savings heuristic algorithm (CW) followed by an improvement phase and a local search phase is developed to solve the TSRP-MMD. The integer program is used to find optimum solutions for small-scale problems. The computational results show that the developed heuristics can be efficiently used to solve the problem.     

A discrete-convex programming approach to the simultaneous optimization of land use and transportation

Three design problems are discussed in this article. First, it is shown that the network design problem with congestion reduces to an all-or nothing traffic assignment problem under some assumptions on the congestion function and the investment cost function. Second, the land use design problem is formulated as an extension of the Koopmans-Beckmann problem and a heuristic is proposed to solve this problem. Third, it is shown that the seemingly more complex problem of designing jointly a land-use plan and a transportation network reduces to a pure land-use design problem. All that is needed to solve the joint optimization problem is a shortest path algorithm and a heuristic to solve the land use design problem. Computational experience is reported for each algorithm.     

Network-based real option models

Building on earlier work to incorporate real option methodologies into network modeling, two models are proposed. The first is the network option design problem, which maximizes the expanded net present value of a network investment as a function of network design variables with the option to defer the committed design investment. The problem is shown to be a generalized version of the network design problem and the multi-period network design problem. A heuristic based on radial basis functions is used to solve the problem for continuous link expansion with congestion effects. The second model is a link investment deferral option set, which decomposes the network investment deferral option into individual, interacting link or project investments. This model is a project selection problem under uncertainty, where each link or project can be deferred such that the expanded net present value is maximized. The option is defined in such a way that a lower bound can be solved using an exact method based on multi-option least squares Monte Carlo simulation. Numerical tests are conducted with the classical Sioux Falls network and compared to earlier published results.     

Transit network design for small-medium size cities

This paper proposes a novel heuristic to solve the network design problem for public transport in small-medium size cities. Such cities can be defined as those with a diameter of a few kilometers with up to a few hundred thousand residents. These urban centers present a specific spatial configuration affecting the land use and mobility system. Transportation demand is widespread in origin and concentrated in a small number of attraction points close to each other. This particular structure of demand (‘many-to-few’) suggests the need for specific methodologies for the design of a transit system at a network level. In this paper, such design methodologies are defined in terms of models and solution procedures and tested on a selected case study. The solution methods show promising results. The key variables of the model are the routes and their frequencies. The constraints of the problem affect the overall demand to be served, the quality of the proposed service (transfer, load factors) and the definition of routes.     

An artificial neural network approach for evaluating transportation network improvements

As demand increases over time, new links or improvements in existing links may be considered for increasing a network's capacity. The selection and timing of improvement projects is an especially challenging problem when the benefits or costs of those projects are interdependent. Most existing models neglect the interdependence of projects and their impacts during intermediate periods of a planning horizon, thus failing to identify the optimal improvement program. A multiperiod network design model is proposed to select the best combination of improvement projects and schedules. This model requires the evaluation of numerous network improvement alternatives in several time periods. To facilitate efficient solution methods for the network design model, an artificial neural network approach is proposed for estimating total travel times corresponding to various project selection and scheduling decisions. Efficient procedures for preparing an appropriate training data set and an artificial neural network for this application are discussed. The Calvert County highway system in southern Maryland is used to illustrate these procedures and the resulting performance.     

A graphical approach to identify sensor locations for link flow inference

Information of link flows in a traffic network becomes increasingly critical in contemporary transportation practice and researches. The network sensor installation is carried out to supply such information. In this paper, we present a graphical approach to determine the smallest subset of links in a traffic network for counting sensor installation, so as to infer the flows on all remaining links. The elegant assumption-free character of the problem introduced by Hu, Peeta and Chu is still kept in this approach. This study points out the topological tree feature of solutions that makes it possible for traffic management agencies to easily and flexibly select links for sensor installation in practice. Addressing from the same graphical perspective, we provide solutions to four other important problems about sensor locations. The preceding two problems are, in traffic networks that already have sensors installed on some links, to identify the subset of links on which link flows can be inferred from sensor measurements and to determine the smallest subset of links on which counting sensors also need to be installed so as to infer link flows on all remaining non-equipped links. The third is to identify the optimal locations for a given number of sensors so as to infer flows on as many links as possible by gradually enlarging the number of links included in circuits. The last one is to determine the smallest subset of links on which to install sensors, in such a way that it becomes possible at the same time to satisfy prior requirements and infer the flows on all remaining links, through building a minimum spanning tree. These methods can be applied to all kinds of long-term planning and link-based applications in traffic networks.     

Application of optimal subset selection to problems of design and scheduling in urban transportation networks

The paper describes some possibilities for modifying the optimal network algorithm developed by Boyce, Farhi and Weischedel in a way that makes it applicable to some practical problems of network planning. The modifications, which have been tested with respect to their effect on the efficiency of the algorithm, include the introduction of asymmetrical demand structures, the integration of an existing network, the lexico-minimization of a dynamic objective function, and the consideration of constraints related to interdependencies between candidate links. Two small network problems and one medium-sized problem (61 nodes, 104 links, 16 candidates) have been computed; the results support the hypothesis that the algorithm may be applied to produce approximate solutions to problems of practical dimensions within a reasonable range of time.     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.     

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.     

Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem

We develop an O(N²) heuristic to solve the single vehicle many-to-many Euclidean Dial-A-Ride problem. The heuristic is based on the Minimum Spanning Tree of the modes of the problem. The algorithm's worst case performance is four times the length of the optimal Dial-A-Ride tour. An analysis of the algorithm's average performance reveals that in terms of sizes of single-vehicle problems that are likely to be encountered in the real world (up to 100 nodes) and in terms of computational complexity, the O(N²) heuristic performs equally well, or, in many cases, better than heuristics described earlier by Stein for the same problem. The performance of the heuristic exhibits statistical stability over a broad range of problem sizes.     

Optimal shipment decisions for an airfreight forwarder: Formulation and solution methods

We study the freight forwarder’s shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewise-linear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipment-ready times.After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.