A Survey of Transportation Problems
---
paper_title: Tramp ship routing and scheduling with speed optimization

paper_content:

Abstract Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Traditionally, models for ship routing and scheduling problems are based on fixed speed and a given fuel consumption rate for each ship. However, in real life a ship’s speed is variable within an interval, and fuel consumption per time unit can be approximated by a cubic function of speed. Here we present the tramp ship routing and scheduling problem with speed optimization, where speed on each sailing leg is introduced as a decision variable. We present a multi-start local search heuristic to solve this problem. To evaluate each move in the local search we have to determine the optimal speed for each sailing leg of a given ship route. To do this we propose two different algorithms. Extensive computational results show that the solution method solves problems of realistic size and that taking speed into consideration in tramp ship routing and scheduling significantly improves the solutions.
---
paper_title: Development of a National Marine Oil Transportation System Model

paper_content:

Abstract This paper presents the development of a model of the marine oil transportation in the United States. NMOTSM, the National Marine Oil Transportation System Model, is a high-level strategic decision-making tool that will be used to systematically identify causes of oil spills and prioritize oil pollution R and D needs for prevention and response. Three distinct phases in the analysis are identified, namely the formulation of the oil transport model, the risk and safety performance assessment and the evaluation of potential prevention, and response measures and approaches.
---
paper_title: Reducing air traffic delay in a space-time network

paper_content:

The author describes a formulation of National Airspace System (NAS) traffic management problem as a multicommodity minimum cost flow problem over a network in space-time. It is a formulation of the multidestination delay minimization problem of managing traffic in the NAS. The model's potential for improving over present practice is described in terms of six assumptions of present practice. The space-time network model can address uncertainty in capacity values, restrictive airways capacities, and hubbing. The minimum cost flow formulation further assumes that attempted entries into the system are deterministic, not Poisson, and that actual entries are controllable. The formulation specifically allows dynamic capacities and possesses good potential for short execution time. >
---
paper_title: Fleet management models and algorithms for an oil-tanker routing and scheduling problem

paper_content:

This paper explores models and algorithms for routing and scheduling ships in a maritime transportation system. The principal thrust of this research effort is focused on the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector, and any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this paper. The resulting mathematical formulation is rather complex to solve due to the integrality conditions and the overwhelming size of the problem for a typical demand contract scenario. Consequently, an alternate aggregate model that retains the principal features of the KPC problem is formulated. The latter model is computationally far more tractable than the initial model, and a specialized rolling horizon heuristic is developed to solve it. The proposed heuristic procedure enables us to derive solutions for practical sized problems that could not be handled by directly solving even the aggregate model. The initial formulation is solved using CPLEX-4.0-MIP capabilities for a number of relatively small-sized test cases, whereas for larger problem instances, the aggregate formulation is solved using CPLEX-4.0-MIP in concert with the developed rolling horizon heuristic, and related results are reported. An ad-hoc routing procedure that is intended to simulate the current KPC scheduling practice is also described and implemented. The results demonstrate that the proposed approach substantially improves upon the results obtained using the current scheduling practice at KPC.
---
paper_title: Multi-Airport Ground Holding Problem: A Heuristic Approach Based on Priority Rules

paper_content:

In recent years, many sophisticated mathematical models have been proposed to address the problem of reducing congestion at major airports by means of Ground Holding (GH) Policies, i.e., by imposing a ground delay to selected aircraft in order to reduce and possibly to avoid airborne delays and congestion. These models, which are usually optimization models, have found little application in practice so far, probably because they are not easy to understand. In this paper we introduce and analyze a family of simple, easy to understand, heuristics. Each heuristic is based on a specific “priority rule”. The flights are grouped dynamically into a manageable number of classes. Each “priority rule” specifies, for any two flights of different classes, which one has priority over the other. The performances of the proposed heuristics are compared among themselves, and with that of an “optimal” policy, on a set of test problems.
---
paper_title: Optimal fleet design in a ship routing problem

paper_content:

Abstract The problem of deciding an optimal fleet (the type of ships and the number of each type) in a real liner shipping problem is considered. The liner shipping problem is a multi-trip vehicle routing problem, and consists of deciding weekly routes for the selected ships. A solution method consisting of three phases is presented. In phase 1, all feasible single routes are generated for the largest ship available. Some of these routes will use only a small portion of the ship’s capacity and can be performed by smaller ships at less cost. This fact is used when calculating the cost of each route. In phase 2, the single routes generated in phase 1 are combined into multiple routes. By solving a set partitioning problem (phase 3), where the columns are the routes generated in phases 1 and 2, we find both the optimal fleet and the coherent routes for the fleet.
---
paper_title: Minimizing the number of tankers to meet a fixed schedule

paper_content:

Abstract : It is shown that the problem of determining the minimum number of carriers required to meet a fixed schedule of transportation can be made into a linear programming problem.
---
paper_title: Optimization of stowage plans for RoRo ships

paper_content:

International vehicle transportation is primarily conducted using Roll-on/Roll-off (RoRo) ships, which are specialized to transport cargo on wheels such as cars, farming equipment, and military equipment. RoRo ships operate by going between different regions of the world according to predefined plans. In this work we focus on operational decisions that are required when operating a fleet of RoRo ships: given a ship set to travel according to a given route, we consider decisions such as which cargoes to carry, how many vehicles to carry from each cargo, and how to stow the vehicles carried during the voyage. A mathematical model is made describing the problem, and both a standard MIP solver and a specially designed heuristic method are used to solve the problem. Computational tests are conducted to analyze the difficulty of solving several variations of the problem. For certain types of instances the MIP solver works well, while for other types the heuristic is very fast and more accurate than the MIP solver.
---
paper_title: The Airline Crew Scheduling Problem: A Survey

paper_content:

This is a survey of the different approaches studied by a number of airlines in the past few years to attempt to optimize the allocation of crews to flights. The approach is usually one of integer programming with 0-1 variables, the matrix of coefficients having a very special form. The survey covers the generation, costing, reduction, and optimization of such matrices.
---
paper_title: The Air Traffic Flow Management with Dynamic Capacity and Co-evolutionary Genetic Algorithm

paper_content:

The quickly increasing of airport flow without suitable support resources is the major cause for congestions and delays. In order to take better use of airport capacity, the air traffic flow management model with dynamic capacity has been developed in this paper based on MAGHP (multi-airport ground holding problem), and a new algorithm, co-evolutionary genetic algorithm (co-GA) is proposed for this model. The airport capacity is considered to be determinate in the original model; and the airborne holding can be transformed to the ground completely. But actually the relationship between the departure and arrival capacity can be presented by curves according to different runway configurations, weather conditions and so on. Besides, airborne holding can not be avoided in certain congested airports sometimes. So the departure and arrival capacities are considered to be variables according to the demands in this paper, and in order to minimize the cost of both airborne and ground holding we assign controlled slot to the flight based on the best allocation of arrivals and departures by the co-GA. The model and co-GA was validated by practical data from Beijing, Shanghai and Guangzhou ATC Centers of the Civil Aviation Administration of China.
---
paper_title: Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model

paper_content:

Abstract This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.
---
paper_title: A Combinatorial Optimization Approach to Aircraft Sequencing Problem

paper_content:

In this paper a combinatorial optimization approach to aircraft sequencing problem is proposed. In particular the single runway case, with the hypotesis that airplanes wait to land at different times, is considered.
---
paper_title: A computer-based decision support system for vessel fleet scheduling: experience and future research

paper_content:

Most ocean shipping companies do the planning of fleet schedules manually based on their experience. Only a few use optimization-based decision support systems (DSS). This paper presents TurboRouter, a decision support system for vessel fleet scheduling, as well as some of the experience gathered from a research project to develop commercial software that is now used by several shipping companies. Perhaps the most important experience is that when designing such systems, the focus should be directed more to the interaction between the user and the system than the optimization algorithm, which has often been the case.
---
paper_title: Vessel allocation by linear programming

paper_content:

This paper presents a linear programming model of a fleet of vessels which is required to transport quantities of cargo, such as coal, iron ore, limestone, and salt from certain producing ports to specific destination ports. This model has been implemented and is currently being used both for planning purposes and as an aid in scheduling the trips to be made by each vessel.
---
paper_title: Reducing air traffic delay in a space-time network

paper_content:

The author describes a formulation of National Airspace System (NAS) traffic management problem as a multicommodity minimum cost flow problem over a network in space-time. It is a formulation of the multidestination delay minimization problem of managing traffic in the NAS. The model's potential for improving over present practice is described in terms of six assumptions of present practice. The space-time network model can address uncertainty in capacity values, restrictive airways capacities, and hubbing. The minimum cost flow formulation further assumes that attempted entries into the system are deterministic, not Poisson, and that actual entries are controllable. The formulation specifically allows dynamic capacities and possesses good potential for short execution time. >
---
paper_title: Multi-Airport Ground Holding Problem: A Heuristic Approach Based on Priority Rules

paper_content:

In recent years, many sophisticated mathematical models have been proposed to address the problem of reducing congestion at major airports by means of Ground Holding (GH) Policies, i.e., by imposing a ground delay to selected aircraft in order to reduce and possibly to avoid airborne delays and congestion. These models, which are usually optimization models, have found little application in practice so far, probably because they are not easy to understand. In this paper we introduce and analyze a family of simple, easy to understand, heuristics. Each heuristic is based on a specific “priority rule”. The flights are grouped dynamically into a manageable number of classes. Each “priority rule” specifies, for any two flights of different classes, which one has priority over the other. The performances of the proposed heuristics are compared among themselves, and with that of an “optimal” policy, on a set of test problems.
---
paper_title: On the Formulation and Solution of the Convoy Routing Problem

paper_content:

In this work, we will identify important variables that contribute to vehicular movement in an emergency environment. In particular, we formulate and pose the convoy routing problem. We suggest a method for modeling the problem and formulate a precise problem statement that significantly reduces the number of variables under consideration relative to similar previous work; even so, we prove that the decision version of this problem is NP-complete. After devising an algorithm using artificial intelligence techniques, we then empirically analyze this model (via software simulation) to get computational results on a single instance of the problem.
---
paper_title: Solving bus terminal location problems using evolutionary algorithms

paper_content:

Bus terminal assignment with the objective of maximizing public transportation service is known as bus terminal location problem (BTLP). We formulate the BTLP, a problem of concern in transportation industry, as a p-uncapacitated facility location problem (p-UFLP) with distance constraint. The p-UFLP being NP-hard (Krarup and Pruzan, 1990), we propose evolutionary algorithms for its solution. According to the No Free Lunch theorem and the good efficiency of the distinctive preserve recombination (DPX) operator, we design a new recombination operator for solving a BTLP by new evolutionary and memetic algorithms namely, genetic local search algorithms (GLS). We also define the potential objective function (POF) for the nodes and design a new mutation operator based on POF. To make the memetic algorithm faster, we estimate the variation of the objective function based on POF in the local search as part of an operator in memetic algorithms. Finally, we explore numerically the performance of nine proposed algorithms on over a thousand randomly generated problems and select the best two algorithms for further testing. The comparative studies show that our new hybrid algorithm composing the evolutionary algorithm with the GLS outperforms the multistart simulated annealing algorithm.
---
paper_title: The Airline Crew Scheduling Problem: A Survey

paper_content:

This is a survey of the different approaches studied by a number of airlines in the past few years to attempt to optimize the allocation of crews to flights. The approach is usually one of integer programming with 0-1 variables, the matrix of coefficients having a very special form. The survey covers the generation, costing, reduction, and optimization of such matrices.
---
paper_title: Scheduling of single stage assembly with air transportation in a consumer electronic supply chain

paper_content:

Consumer electronics supply chain being a booming industry with intensive competition, multinational organizations are rapidly moving towards global manufacturing networks to minimize the costs and improve delivery efficiency. The studies on modeling and scheduling of global supply chains in consumer electronics industry have lead to growing interests in recent years. In this paper, the problem of synchronized scheduling of assembly with air transportation to minimize delivery costs is addressed. The overall problem is decomposed into sub-problems viz., the air transportation allocation problem and assembly scheduling problem. The air transportation allocation problem is shown to have the structure of the regular transportation problem, while the assembly scheduling problem is shown to be NP-hard. We investigate the case of process delays in assembly for reasons such as machine breakdowns, shortages of materials, etc., and present a schedule repair heuristic. We evaluate the performance of the proposed heuristic with industry practice methods by testing the heuristics on randomly generated problems of size varying from 20 to 100 jobs.
---
paper_title: The Air Traffic Flow Management with Dynamic Capacity and Co-evolutionary Genetic Algorithm

paper_content:

The quickly increasing of airport flow without suitable support resources is the major cause for congestions and delays. In order to take better use of airport capacity, the air traffic flow management model with dynamic capacity has been developed in this paper based on MAGHP (multi-airport ground holding problem), and a new algorithm, co-evolutionary genetic algorithm (co-GA) is proposed for this model. The airport capacity is considered to be determinate in the original model; and the airborne holding can be transformed to the ground completely. But actually the relationship between the departure and arrival capacity can be presented by curves according to different runway configurations, weather conditions and so on. Besides, airborne holding can not be avoided in certain congested airports sometimes. So the departure and arrival capacities are considered to be variables according to the demands in this paper, and in order to minimize the cost of both airborne and ground holding we assign controlled slot to the flight based on the best allocation of arrivals and departures by the co-GA. The model and co-GA was validated by practical data from Beijing, Shanghai and Guangzhou ATC Centers of the Civil Aviation Administration of China.
---
paper_title: A heuristic method for the inventory routing problem with time windows

paper_content:

This paper is to resolve the VRPTW and the inventory control decision problem simultaneously since both the vehicle routing decision with time windows and the inventory control decision affect each other and must be considered together. A mathematical model of inventory routing problem with time windows (IRPTW) is proposed. Since finding the optimal solution(s) for IRPTW is a NP-hard problem, this paper proposes a two-phase heuristic method. The first phase is to find the initial solution. The second phase is to improve the solution adopting the variable neighborhood tabu search (VNTS) selecting better neighborhood solutions, to obtain the optimal solution. Moreover, the proposed method was compared with three other heuristic methods. The experimental results indicate that the proposed method is better than the three other methods in terms of average supply chain cost (transportation cost, time window violation penalty cost and inventory cost).
---
paper_title: A Combinatorial Optimization Approach to Aircraft Sequencing Problem

paper_content:

In this paper a combinatorial optimization approach to aircraft sequencing problem is proposed. In particular the single runway case, with the hypotesis that airplanes wait to land at different times, is considered.
---
paper_title: Bus routing in a multi-school system

paper_content:

Abstract This paper describes and evaluates a practical computer based method for translating data concerning (1) the location of each school in a multi-school system to be serviced by a bus fleet, (2) the location of each student to be transported to each school, (3) the time period during which students assigned to each school are to be transported, and (4) the available bus facilities into a set of bus routes which specify school-to-school sequencing of each bus and the stop-to-stop route to be followed in traveling to every school. Each route is designed so that bus capacity and student riding time constraints are satisfied while attempting to minimize both total bus travel time (including running empty) and the number of routes required to service all the stops associated with the school. The mathematical models developed were programmed in FORTRAN IV for use on a CDC 6400 computer and were applied to four schools in a Western New York school district. For each school the routing system determined by these mathematical models was better in terms of number of buses and/or travel time than the system in current use. Furthermore, computation time was very reasonable (from 6.9 sec for 596 students, 37 stops to 136.9 sec for 1097 students, 76 stops).
---
paper_title: The Inventory Routing Problem

paper_content:

The role of logistics management is changing. Many companies are realizing that value for a customer can, in part, be created through logistics management (Langley and Holcomb, 1996). Customer value can be created through product availability, timeliness and consistency of delivery, ease of placing orders, and other elements of logistics service. Consequently, logistics service is becoming recognized as an essential element of customer satisfaction in a growing number of product markets today.
---
paper_title: Methodologies for synchronised scheduling of assembly and air transportation in a consumer electronics supply chain

paper_content:

Motivated by a major PC manufacturer in the consumer electronics industry, we study the problem of synchronisation of assembly manufacturing and final deliveries using air transportation to achieve accurate delivery with minimised delivery cost in consumer electronics supply chain (CESC). The customer orders are shipped to the customers by cargo flights. Orders are allocated to the available flight capacities based on customer delivery dates. Synchronisation is considered to match the assembly completion of each order with the departure time of its predetermined allocated flights. We break the synchronisation problem down into two sub-problems consisting of an air transportation allocation problem and an assembly scheduling problem. The first sub-problem is formulated as an Integer Linear Programming (ILP) model. Two solution methodologies are proposed for the second sub-problem. Computational results indicate that the proposed methodologies can achieve considerable cost reduction compared to the existing industry practice.
---
paper_title: On an Integer Program for a Delivery Problem

paper_content:

An actual truck delivery problem of general applicability is stated as an integer program. The successful computational performance of Gomory's "cutting plane" algorithm for a set of nine particular problems is discussed. Finally, the structure of the general problem is shown to be a natural generalization of covering problems of graph theory.
---
paper_title: The team orienteering problem

paper_content:

In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail.
---
paper_title: The open vehicle routing problem: Algorithms, large-scale test problems, and computational results

paper_content:

In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route. The description of this variant of the standard vehicle routing problem appeared in the literature over 20 years ago, but has just recently attracted the attention of practitioners and researchers. Today, the OVRP is encountered in practice in the home delivery of packages and newspapers. Contractors who are not employees of the delivery company use their own vehicles and do not return to the depot. In the last five years, tabu search, deterministic annealing, and large neighborhood search have been applied to the OVRP with some success. In this paper, we review OVRP algorithms, develop a variant of our record-to-record travel algorithm for the standard vehicle routing problem to handle open routes, and report computational results on test problems taken from the literature. Finally, we develop a set of eight large-scale problems that range in size from 200 to 480 nodes and report solutions generated by our record-to-record travel algorithm on this test set.
---
paper_title: A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem

paper_content:

Cash transportation vehicle routing and scheduling are essential for security carriers to minimize their operating costs and ensure safe cash conveyance. In real operations, to increase cash conveyance safety, there must be significant variation in daily cash transportation vehicle routes and schedules, making such vehicle routes and schedules difficult to formulate. However, for convenient planning purposes, security carriers normally plan such routes and schedules based on personal experience, without considering variations in routes and schedules from a system perspective. As a result, the obtained routes and schedules are neither safe nor efficient for transporting cash. In this study, a model is developed where the time-space network technique is utilized to formulate the potential movements of cash transportation vehicles among all demand points in the dimensions of time and space. This model incorporates a new concept of similarity of time and space for routing and scheduling, which is expected to help security carriers formulate more flexible routing and scheduling strategies. This is helpful to reduce the risk of robbery. Mathematically, the model is formulated as an integer multiple-commodity network flow problem. A solution algorithm, based on a problem decomposition/collapsing technique, coupled with the use of a mathematical programming software, is developed to efficiently solve the problem. The case study results show that our model and solution algorithm could be useful references for security carriers in actual practice.
---
paper_title: An approach for solving a class of transportation scheduling problems

paper_content:

Abstract An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient.
---
paper_title: The Truck Dispatching Problem

paper_content:

The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. The shortest routes between any two points in the system are given and a demand for one or several products is specified for a number of stations within the distribution system. It is desired to find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage covered by the fleet is a minimum A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may be readily performed by hand or by an automatic digital computing machine. No practical applications of the method have been made as yet. A number of trial problems have been calculated, however.
---
paper_title: On the Formulation and Solution of the Convoy Routing Problem

paper_content:

In this work, we will identify important variables that contribute to vehicular movement in an emergency environment. In particular, we formulate and pose the convoy routing problem. We suggest a method for modeling the problem and formulate a precise problem statement that significantly reduces the number of variables under consideration relative to similar previous work; even so, we prove that the decision version of this problem is NP-complete. After devising an algorithm using artificial intelligence techniques, we then empirically analyze this model (via software simulation) to get computational results on a single instance of the problem.
---
paper_title: A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars

paper_content:

The purpose of this article is to propose a tabu search heuristic for the split delivery Vehicle Routing Problem with Production and Demand Calendars (VRPPDC). This new problem consists of determining which customers will be served by a common carrier, as well as the delivery routes for those served by the private fleet, in order to minimize the overall transportation and inventory costs. We first model this problem and then propose a simple decomposition procedure that can be used to provide a starting solution. Next, we introduce a new tabu search heuristic and we describe two new neighbor reduction strategies. Finally, we present the results of our extensive computational tests. According to these tests, our reduction strategies are efficient not only at reducing computing time but also at improving the overall solution quality.
---
paper_title: The school bus routing problem: A review

paper_content:

This paper aims to provide a comprehensive review of the school bus routing problem (SBRP). SBRP seeks to plan an efficient schedule for a fleet of school buses where each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school. This class of problem consists of different sub-problems involving data preparation, bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. In this paper, the various assumptions, constraints, and solution methods used in the literature on SBRP are summarized. A list of issues requiring further research is also presented.
---
paper_title: An Algorithm for Combining Truck Trips

paper_content:

This paper presents a method for serial combination of truck trips to minimize the total cost of deadheading, subject to constraints on the allowed combinations. The problem is initially formulated as an integer transportation problem with extra compatibility constraints, and then reduced to a classical transportation problem. Modifications of the classical algorithm led to a fifty-fold reduction in computer time, and permit solution of a 1000 × 1000 problem in less than two minutes of computer time. Implementation of the method led to considerable cost savings over the older manual procedure.
---
paper_title: Solving bus terminal location problems using evolutionary algorithms

paper_content:

Bus terminal assignment with the objective of maximizing public transportation service is known as bus terminal location problem (BTLP). We formulate the BTLP, a problem of concern in transportation industry, as a p-uncapacitated facility location problem (p-UFLP) with distance constraint. The p-UFLP being NP-hard (Krarup and Pruzan, 1990), we propose evolutionary algorithms for its solution. According to the No Free Lunch theorem and the good efficiency of the distinctive preserve recombination (DPX) operator, we design a new recombination operator for solving a BTLP by new evolutionary and memetic algorithms namely, genetic local search algorithms (GLS). We also define the potential objective function (POF) for the nodes and design a new mutation operator based on POF. To make the memetic algorithm faster, we estimate the variation of the objective function based on POF in the local search as part of an operator in memetic algorithms. Finally, we explore numerically the performance of nine proposed algorithms on over a thousand randomly generated problems and select the best two algorithms for further testing. The comparative studies show that our new hybrid algorithm composing the evolutionary algorithm with the GLS outperforms the multistart simulated annealing algorithm.
---
paper_title: A truck loading problem

paper_content:

A vehicle with m compartments transports q different products of various sizes from a source to n different destinations. The operational problem is how to load the compartments of the vehicle so that the replenishment time is maximized for a given route of destinations. A mixed integer linear programming model is developed for this class of problems. An investigation of the structure of the model reveals that a subproblem can be obtained in the form of a weighted distribution problem. Consequently, a simple subalgorithm finds an integer solution to this subproblem. The main algorithm bisects the interval of uncertainty until it becomes sufficiently small. There is another subalgorithm to test whether a feasible solution exists in the final interval of uncertainty by solving a Phase I problem. Our numerical experience has shown its computational efficiency and the quality of the solutions obtained. A problem of size 30 can be solved by this method in a fraction of a second. Further, an optimal solution is obtained in 82% of the randomly chosen problems.
---
paper_title: Structuring Multi-attribute Value Hierarchies

paper_content:

The first stage in a multi-attribute value analysis is the development of a hierarchical structure of the attributes of the problem. This paper reports the process of developing such a structure for the problem of choosing a suitable mode of transport for radioactive waste. The initial hierarchy of attributes went through several stages of development as new insights emerged about the nature of the problem. Some of the reasons behind this restructuring are discussed, and several important questions about the structuring process are formulated.
---
paper_title: A heuristic method for the inventory routing problem with time windows

paper_content:

This paper is to resolve the VRPTW and the inventory control decision problem simultaneously since both the vehicle routing decision with time windows and the inventory control decision affect each other and must be considered together. A mathematical model of inventory routing problem with time windows (IRPTW) is proposed. Since finding the optimal solution(s) for IRPTW is a NP-hard problem, this paper proposes a two-phase heuristic method. The first phase is to find the initial solution. The second phase is to improve the solution adopting the variable neighborhood tabu search (VNTS) selecting better neighborhood solutions, to obtain the optimal solution. Moreover, the proposed method was compared with three other heuristic methods. The experimental results indicate that the proposed method is better than the three other methods in terms of average supply chain cost (transportation cost, time window violation penalty cost and inventory cost).
---
paper_title: On the tour planning problem

paper_content:

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
---
paper_title: Bus routing in a multi-school system

paper_content:

Abstract This paper describes and evaluates a practical computer based method for translating data concerning (1) the location of each school in a multi-school system to be serviced by a bus fleet, (2) the location of each student to be transported to each school, (3) the time period during which students assigned to each school are to be transported, and (4) the available bus facilities into a set of bus routes which specify school-to-school sequencing of each bus and the stop-to-stop route to be followed in traveling to every school. Each route is designed so that bus capacity and student riding time constraints are satisfied while attempting to minimize both total bus travel time (including running empty) and the number of routes required to service all the stops associated with the school. The mathematical models developed were programmed in FORTRAN IV for use on a CDC 6400 computer and were applied to four schools in a Western New York school district. For each school the routing system determined by these mathematical models was better in terms of number of buses and/or travel time than the system in current use. Furthermore, computation time was very reasonable (from 6.9 sec for 596 students, 37 stops to 136.9 sec for 1097 students, 76 stops).
---
paper_title: Optimizing departure times in vehicle routes

paper_content:

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

paper_content:

Abstract A solution construction method and a tabu search improvement heuristic coupled with the deviation concept found in deterministic annealing is developed to solve the truck and trailer routing problem. We test our tabu search method on 21 problems that have been converted from the basic vehicle routing problem. Our construction method always solves a problem (it always finds a feasible solution) and the tabu search improvement heuristic significantly improves an initial solution. Scope and purpose The vehicle routing problem holds a central place in distribution management and logistics, and its practical significance has been well documented in the literature. The truck and trailer routing problem is a variant of the vehicle routing problem to take into account some real-life applications in which fleet of m k trucks and m l trailers ( m k ⩾ m l ) services a set of customers. Some customers can be serviced by a complete vehicle (that is, a truck pulling a trailer) or by a truck alone, whereas others can be serviced only a truck alone. There are three types of routes in a solution to the problem: (1) a pure truck route traveled by a truck alone, (2) a pure vehicle route without any sub-tours traveled by a complete vehicle, and (3) a complete vehicle route consisting of a main tour traveled by a complete vehicle, and one or more sub-tours traveled by a truck alone. A sub-tour begins and finishes at a customer on the main tour where the truck uncouples, parks, and re-couples its pulling trailer and continues to service the remaining customers on the sub-tour. The objective is to minimize the total distance traveled, or total cost incurred by the fleet. The problem is more difficult to solve than the basic vehicle routing problem, but it occurs in many real-life applications. The purpose of this article is to develop a solution method that generates an initial solution and improves the solution using tabu search. The tabu search procedure uses the deviation concept found in deterministic annealing to further improve the initial solution. Our heuristic solves the truck and trailer routing problem efficiently and effectively.
---
paper_title: An exact algorithm for the petrol station replenishment problem

paper_content:

In the petrol station replenishment problem (PSRP), the aim is to deliver petroleum products to petrol stations by means of an unlimited heterogeneous fleet of compartmented tank trucks. The problem consists of jointly determining quantities to deliver within a given interval, of allocating products to tank truck compartments and of designing delivery routes to stations. This article describes an exact algorithm which decomposes the PSRP into a truck loading problem and a routing problem. An algorithm which makes use of assignment, optimality tests and possibly standard ILP algorithm is proposed to solve the loading problem. The routing problem is handled using two different strategies, based either on a matching approach or on a column generation scheme. This algorithm was extensively tested on randomly generated data and on a real-life case arising in Eastern Quebec.
---
paper_title: The petrol station replenishment problem with time windows

paper_content:

In the Petrol Station Replenishment Problem with Time Windows (PSRPTW) the aim is to optimize the delivery of several petroleum products to a set of petrol stations using a limited heterogeneous fleet of tank-trucks. More specifically, one must determine the quantity of each product to deliver, the assignment of products to truck compartments, delivery routes, and schedules. The objective is to maximize the total profit equal to the sales revenue, minus the sum of routing costs and of regular and overtime costs. This article first proposes a mathematical formulation of the PSRPTW. It then describes two heuristics based on arc preselection and on route preselection. Extensive computational tests on randomly generated instances confirm the efficiency of the proposed heuristics. Finally, a performance analysis on a real case shows a distance reduction of more than 20% over a solution obtained by an experienced dispatcher.
---
paper_title: A heuristic for the multi-period petrol station replenishment problem

paper_content:

In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology.
---
paper_title: The Inventory Routing Problem

paper_content:

The role of logistics management is changing. Many companies are realizing that value for a customer can, in part, be created through logistics management (Langley and Holcomb, 1996). Customer value can be created through product availability, timeliness and consistency of delivery, ease of placing orders, and other elements of logistics service. Consequently, logistics service is becoming recognized as an essential element of customer satisfaction in a growing number of product markets today.
---
paper_title: Transport Logistics Planning with Service-Level Constraints

paper_content:

In this paper, we study a logistics problem arising in military transport planning. A military organization operates a large fleet of vehicles in a depot to serve the requests of various operational units. Each request has a fixed start and end time, and is served by a prescribed number of vehicles. We address the following two problems: (1) how many vehicles are at least needed to meet a given service level of requests; and (2) suppose we allow each request to shift its start time by a constant duration, call all the requests be met? A Niche genetic algorithm, together with a hybridized variant, are applied to the problem.
---
paper_title: Operations Research in Passenger Railway Transportation

paper_content:

In this paper we give an overview of state-of-the-art Operations Research models and techniques used in passenger railway transportation. For each planning phase (strategic, tactical and operational), we describe the planning problems arising there and discuss some models and algorithms to solve them. We do not only consider classical, well-known topics such as timetabling, rolling stock scheduling and crew scheduling, but we also discuss some recently developed topics such as shunting and reliability of timetables. ::: ::: Finally, we focus on several practical aspects for each of these problems at the largest Dutch railway operator, NS Reizigers.
---
paper_title: On the tour planning problem

paper_content:

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
---
paper_title: A Survey of Optimization Models for Train Routing and Scheduling

paper_content:

The aim of this paper is to present a survey of recent optimization models for the most commonly studied rail transportation problems. For each group of problems, we propose a classification of models and describe their important characteristics by focusing on model structure and algorithmic aspects. The review mainly concentrates on routing and scheduling problems since they represent the most important portion of the planning activities performed by railways. Routing models surveyed concern the operating policies for freight transportation and railcar fleet management, whereas scheduling models address the dispatching of trains and the assignment of locomotives and cars. A brief discussion of analytical yard and line models is also presented. The emphasis is on recent contributions, but several older yet important works are also cited.
---
paper_title: The Locomotive Routing Problem

paper_content:

Given a schedule of trains, the locomotive planning (or scheduling) problem (LPP) is to determine the minimum cost assignment of locomotive types to trains that satisfies a number of business and operational constraints. Once this is done, the railroad has to determine the sequence of trains to which each locomotive is assigned by unit number so that it can be fueled and serviced as necessary. We refer to this problem as the locomotive routing problem (LRP). The LRP is a very large scale combinatorial optimization problem, and the general version that we consider has previously been unstudied and unsolved in the research literature. In this paper, we develop robust optimization methods to solve the LRP. There are two major sets of constraints that need to be satisfied by each locomotive route: (1) locomotive fueling constraints, which require that every unit visit a fueling station at least once for every F miles of travel, and (2) locomotive servicing constraints, which require that every unit visit a service station at least once for every S miles of travel. The output of the LPP is not directly implementable because the LPP does not consider these fueling and servicing constraints. The LRP considers these constraints, and its output is therefore implementable. We model the LRP by considering alternative fueling and servicing friendly train paths (or strings) between servicing stations on the network. We formulate the LRP as an integer programming problem on a suitably constructed space-time network and show that this problem is NP-Complete. This integer programming problem has millions of decision variables. We develop a fast aggregation-disaggregation based algorithm to solve the problem within a few minutes of computational time to near optimality. Finally, we present computational results and extensive case studies of our algorithms on real data provided by a major Class I U.S. railroad.
---
paper_title: Concurrent Trajectory and Vehicle Optimization: A Case Study of Earth-Moon Supply Chain Logistics

paper_content:

The objective of this paper is to demonstrate an integrated system design optimization approach for space system networks. The decisions made during the initial design phases for a complex system, will drastically afiect the flnal product at the architectural level. Traditionally, the design process for a complex system involves the sequential design of the sub-system components, which may lead to a sub-optimal system design. In systems with a high degree of sub-system coupling, the ordering of the sub-system design decisions indirectly determines the priority of the sub-systems to the system. In addition, with the announcement of the space exploration initiative, the goal is to design a sustainable space exploration system that can accomplish multiple missions in an environment of uncertainty. As such, we can no longer consider each mission separately, and therefore must integrate the multiple missions into the initial design of the system. By viewing the set of missions as an integrated space network, we add another sub-system to the system design space. A systems level solution to this problem requires that the network, the vehicle, and the trajectory design, be considered concurrently. To illustrate a concurrent design optimization methodology, this paper considers the design of an Earth-Moon supply chain. Speciflcally, we consider the problem of delivering cargo units of water from low Earth orbit to lunar orbit and the lunar surface. The formulation requires that the architectural characteristics of the vehicle used to transport the packages to the destinations and the paths the vehicles travel be determined concurrently. The problem is solved using both traditional design optimization methods and a concurrent design optimization method. The vehicle optimization and concurrent optimization both achieve a minimum system mass of 58,768 kg for a single vehicle design, which is an improvement of 114,070 kg from the network optimization solution. The system objective is further reduced to 47,498 kg when multiple vehicles are designed. Initial investigations into the sensitivity of the solution to changes in demand reveal that the minimum system mass is obtained when direct routes to the demands nodes are travelled.
---
paper_title: Column generation based heuristics for a generalized location routing problem with profits arising in space exploration

paper_content:

The generalized location routing problem with profits is a new routing problem class that combines the vehicle routing problem with profits, depot or base selection, and the notion of strategies and route tactics to be employed at selected bases. The problem simultaneously determines base locations, strategies to use at the bases, sites to visit, and routes to carry out the visits, to maximize the sum of profits that can be obtained by visiting sites, under resource consumption constraints. The problem arises in exploration of planetary bodies where strategies correspond to different technologies. A description of the generalized location routing problem with profits and its mathematical formulation as an integer program are provided. Two solution methodologies to solve the problem – branch-and-price and a three-phase heuristic method combined with a generalized randomized adaptive search procedure – are proposed. Numerical experiments for the two solution methodologies are carried out. Their performance in terms of computation time and optimality gap are analyzed and compared to establish the problem characteristics, indicating which method is more advantageous.
---
paper_title: An approach for solving a class of transportation scheduling problems

paper_content:

Abstract An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient.
---
paper_title: Interplanetary Transfers Between Halo Orbits: Connectivity Between Escape and Capture Trajectories

paper_content:

Spacecraft escape and capture trajectories from or to Halo orbits about the L1 or L2 points using impulsive maneuvers at periapsis of the manifolds for interplanetary transfers are analyzed in the restricted Hill three-body problem. This application is motivated by future proposals to place deep-space ports at the Earth andMars L1 or L2 points. First, the feasibility of interplanetary trajectories between Earth Halo orbits and Mars Halo orbits is investigated. In this study, unstable and stable manifolds associated with the Halo orbits are used to approach the vicinity of the planet’s surface, and use impulsive maneuvers at periapsis for escape and capture trajectories to and from Halo orbits. Interplanetary trajectories between Earth and Mars Halo orbits with reasonable V and flight time are found. Next, applying these dynamics to an Earth–Mars transportation system using spaceports on Earth and Mars Halo orbits, the system is evaluated in terms of the spacecraft mass of round-trip transfer. As a result, transfer between low Earth orbits and low Mars orbits via the planets’ Halo orbits can reduce spacecraft wet mass compared with a direct round-trip transfer, by leaving propellant for the return.
---
paper_title: Solar sail transfer trajectory from L1 point to sub-L1 point

paper_content:

Abstract Solar sail working at a sub-L1 point can increase the warning time for geomagnetic storms. The transfer trajectory consists of launch of the spacecraft from Earth to a halo orbit and transfer phase from the halo orbit to the vicinity of the targeted sub-L1 point. This paper proposes a new transfer profile from the L1 periodic orbits to the sub-L1 point or periodic orbits around it. Both the invariant manifolds of the periodic orbits around L1 point and sub-L1 points are used to design the transfer trajectory. The spacecraft evolves along the unstable manifold of the L1 periodic orbit during pre-sail-deployment phase and flies to the target sub-L1 periodic orbit along its stable manifold after sail deployment. Previous to the transfer trajectory design, the existence of this kind of transfer trajectory is checked from the point of view of energy. Then, the transfer trajectory design problem is parameterized and the design parameters are optimized to achieve the transfer trajectory, both 2-dimensional and 3-dimensional cases. The influences of different design parameters on the transfer trajectory are investigated for 2-dimensional cases. Several 3-dimensional transfer trajectories are used to illustrate the differences from 2-dimensional cases.
---
paper_title: A heuristic for the multi-period petrol station replenishment problem

paper_content:

In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology.
---
paper_title: A Multiperiod Generalized Network Flow Model of the U.S. Integrated Energy System: Part II—Simulation Results

paper_content:

This paper is the second of a two-part paper and describes the application of a multiperiod generalized network flow model that is used to analyze the economic efficiencies of the energy movements from the coal and natural gas suppliers to the electric load centers, providing a simulation tool that captures dynamics of and interdependencies between the coal, natural gas, and electricity networks. The modeling approach, mathematical formulation, and modeling assumptions are presented in part I. This sequel presents and discusses numerical results to illustrate the application of the model. The model enables public and private decision makers to carry out comprehensive analyses of a wide range of issues related to the energy sector, such as strategic planning, economic impact assessment, and different regulatory regimes
---
paper_title: A Numerical Model for Water Flow and Chemical Transport in Variably Saturated Porous Media

paper_content:

A two-dimensional numerical model is developed for the simulation of water flow and chemical transport through variably saturated porous media. The nonlinear flow equation is solved using the Calerkin finite-element technique with either the Picard or the Newton iteration scheme. A continuous velocity field is obtained by separate application of the Galerkin technique to the Darcy's equation. A two-site adsorption-desorption model with a first-order loss term is used to describe the chemical behavior of the reactive solute. The advective part of the transport equation is solved with one-step backward particle tracking while the dispersive part is solved by the regular Galerkin finite-element technique. A precondi tioned conjugate gradient-like method is used for the iterative solution of the systems of linear simultaneous equations to save on computer memory and execution time. The model is applied to a few flow and transport problems, and the numerical results are compared with observed and analytic values. The model is found to duplicate the analytic and observed values quite well, even near very sharp fronts.
---
paper_title: Multi-Airport Ground Holding Problem: A Heuristic Approach Based on Priority Rules

paper_content:

In recent years, many sophisticated mathematical models have been proposed to address the problem of reducing congestion at major airports by means of Ground Holding (GH) Policies, i.e., by imposing a ground delay to selected aircraft in order to reduce and possibly to avoid airborne delays and congestion. These models, which are usually optimization models, have found little application in practice so far, probably because they are not easy to understand. In this paper we introduce and analyze a family of simple, easy to understand, heuristics. Each heuristic is based on a specific “priority rule”. The flights are grouped dynamically into a manageable number of classes. Each “priority rule” specifies, for any two flights of different classes, which one has priority over the other. The performances of the proposed heuristics are compared among themselves, and with that of an “optimal” policy, on a set of test problems.
---
paper_title: Genetic algorithms for coordinated scheduling of production and air transportation

paper_content:

A main issue in supply chain management is coordinating production and distribution decisions. To achieve effective logistics scheduling, it is critical to integrate these two functions and plan them in a coordinated way. The problem is to determine both production schedule and air transportation allocation of orders to optimize customer service at minimum total cost. In order to solve the given problem, two genetic algorithm (GA) approaches are developed. However, the effectiveness of most metaheuristic algorithms is significantly depends on the correct choice of parameters. Hence, a Taguchi experimental design method is applied to set and estimate the proper values of GAs parameters to improve their performance. For the purpose of performance evaluation of proposed algorithms, various problem sizes are utilized and the computational results of GAs are compared with each other. Moreover, we investigate the impacts of the rise in the problem size on the performance of our algorithms.
---
paper_title: Optimizing Arrival Flight Delay Scheduling Based on Simulated Annealing Algorithm

paper_content:

Abstract This paper presents a model based on the simulated annealing algorithm for optimizing arrival flight delays to reduce serious air traffic flight delays. Based on the characteristic of the flights and the thinking of system optimization, this paper builds up dynamic optimizing models of the flight delays scheduling with the objective function of delay cost. The simulated annealing algorithm is also used to solve this problem. This model can reduce the cost and the influence of the delay as much as possible. Data from an airport in China has been used to verify the model.
---
paper_title: An engineering-economic model of pipeline transport of CO2 with application to carbon capture and storage

paper_content:

Abstract Carbon dioxide capture and storage (CCS) involves the capture of CO 2 at a large industrial facility, such as a power plant, and its transport to a geological (or other) storage site where CO 2 is sequestered. Previous work has identified pipeline transport of liquid CO 2 as the most economical method of transport for large volumes of CO 2 . However, there is little published work on the economics of CO 2 pipeline transport. The objective of this paper is to estimate total cost and the cost per tonne of transporting varying amounts of CO 2 over a range of distances for different regions of the continental United States. An engineering-economic model of pipeline CO 2 transport is developed for this purpose. The model incorporates a probabilistic analysis capability that can be used to quantify the sensitivity of transport cost to variability and uncertainty in the model input parameters. The results of a case study show a pipeline cost of US$ 1.16 per tonne of CO 2 transported for a 100 km pipeline constructed in the Midwest handling 5 million tonnes of CO 2 per year (the approximate output of an 800 MW coal-fired power plant with carbon capture). For the same set of assumptions, the cost of transport is US$ 0.39 per tonne lower in the Central US and US$ 0.20 per tonne higher in the Northeast US. Costs are sensitive to the design capacity of the pipeline and the pipeline length. For example, decreasing the design capacity of the Midwest US pipeline to 2 million tonnes per year increases the cost to US$ 2.23 per tonne of CO 2 for a 100 km pipeline, and US$ 4.06 per tonne CO 2 for a 200 km pipeline. An illustrative probabilistic analysis assigns uncertainty distributions to the pipeline capacity factor, pipeline inlet pressure, capital recovery factor, annual O&M cost, and escalation factors for capital cost components. The result indicates a 90% probability that the cost per tonne of CO 2 is between US$ 1.03 and US$ 2.63 per tonne of CO 2 transported in the Midwest US. In this case, the transport cost is shown to be most sensitive to the pipeline capacity factor and the capital recovery factor. The analytical model elaborated in this paper can be used to estimate pipeline costs for a broad range of potential CCS projects. It can also be used in conjunction with models producing more detailed estimates for specific projects, which requires substantially more information on site-specific factors affecting pipeline routing.
---
paper_title: Water Distribution Systems Analysis

paper_content:

A generalized method is presented for solving nonlinear networks and studying their sensitivity under steady-state flow conditions. The network may contain elements other than pipes, such as pumps and valves, and unknowns may be combinations of heads, consumptions or element resistances. Conditions for convergence of the Newton-Raphson iterative scheme and the possibility of insolvable problems are discussed. The method's flexibility for handling changes in input data is used in a time-sharing environment as an on-line tool to assist engineering design and decision making. For effective use, large capacity, high-speed computers are necessary. Traditional cut and try procedures for studying water distribution systems may be greatly improved by effective utilization of on-line data storage and interaction of computer programs to perform analysis, synthesis and information retrieval. Available commercial systems provide this capability.
---
paper_title: Column generation based heuristic for a helicopter routing problem

paper_content:

This work presents a column generation based heuristic algorithm for the problem of planning the flights of helicopters to attend transport requests among airports in the continent and offshore platforms on the Campos basin for the Brazilian State Oil Company (Petrobras). We start from a previous MIP based heuristic for this Helicopter Routing Problem and add column generation procedures that improve the solution quality. This is done by extending the earlier formulation and providing an algorithm to find optimal passenger allocation to fixed helicopter routes. A post optimization procedure completes the resulting algorithm, which is more stable and allows consistently finding solutions that improve the safety and the cost of the one done by the oil company experts.
---
paper_title: The Air Traffic Flow Management with Dynamic Capacity and Co-evolutionary Genetic Algorithm

paper_content:

The quickly increasing of airport flow without suitable support resources is the major cause for congestions and delays. In order to take better use of airport capacity, the air traffic flow management model with dynamic capacity has been developed in this paper based on MAGHP (multi-airport ground holding problem), and a new algorithm, co-evolutionary genetic algorithm (co-GA) is proposed for this model. The airport capacity is considered to be determinate in the original model; and the airborne holding can be transformed to the ground completely. But actually the relationship between the departure and arrival capacity can be presented by curves according to different runway configurations, weather conditions and so on. Besides, airborne holding can not be avoided in certain congested airports sometimes. So the departure and arrival capacities are considered to be variables according to the demands in this paper, and in order to minimize the cost of both airborne and ground holding we assign controlled slot to the flight based on the best allocation of arrivals and departures by the co-GA. The model and co-GA was validated by practical data from Beijing, Shanghai and Guangzhou ATC Centers of the Civil Aviation Administration of China.
---
paper_title: Optimization Model for Water Distribution System Design

paper_content:

A new methodology is developed for determining the optimal (minium‐cost) design of water distribution systems. The components that can be sized are the pipe network, pumps or pump station, and tanks. In addition, the optimal settings for control and pressure‐reducing valves can be determined. This methodology couples nonlinear programming techniques with existing water distribution simulation models. Previous methodologies have typically simplified the system hydraulics to be able to solve the optimization problem. This new methodology retains the generality of the hydraulic simulation model so that the problem is only limited by the ability of the simulation model rather than the optimization model. The methodology uses a generalized reduced gradient model to solve a problem that is reduced in size and complexity by implicitly solving the conservation of mass and energy equations using the hydraulic simulator and an augmented Lagrangian approach to incorporate pressure head bounds in the objective functi...
---
paper_title: On the tour planning problem

paper_content:

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
---
paper_title: The petrol station replenishment problem with time windows

paper_content:

In the Petrol Station Replenishment Problem with Time Windows (PSRPTW) the aim is to optimize the delivery of several petroleum products to a set of petrol stations using a limited heterogeneous fleet of tank-trucks. More specifically, one must determine the quantity of each product to deliver, the assignment of products to truck compartments, delivery routes, and schedules. The objective is to maximize the total profit equal to the sales revenue, minus the sum of routing costs and of regular and overtime costs. This article first proposes a mathematical formulation of the PSRPTW. It then describes two heuristics based on arc preselection and on route preselection. Extensive computational tests on randomly generated instances confirm the efficiency of the proposed heuristics. Finally, a performance analysis on a real case shows a distance reduction of more than 20% over a solution obtained by an experienced dispatcher.
---
paper_title: A Multiperiod Generalized Network Flow Model of the U.S. Integrated Energy System: Part I—Model Description

paper_content:

This paper is the first of a two-part paper presenting a multiperiod generalized network flow model of the integrated energy system in the United States. Part I describes the modeling approach used to evaluate the economic efficiencies of the system-wide energy flows, from the coal and natural gas suppliers to the electric load centers. Under the proposed problem formulation, fuel supply and electricity demand nodes are connected via a transportation network, and the model is solved for the most efficient allocation of quantities and corresponding prices. The methodology includes physical, economic, and environmental aspects that characterize the different networks. Part II of this paper provides numerical results that demonstrate the application of the model
---
paper_title: A dynamic programming approach for the airport capacity allocation problem

paper_content:

In most of the optimization models developed to manage airports operations, arrivals and departures capacities are treated as independent variables: that is the number of flights allowed to take off does not affect the number of landings in any unit of time, and vice versa. This assumption is seldom verified in most of the congested airports, where many interactions between arrivals and departures take place. In this paper, we face the problem of finding the optimal trade‐off between the number of arrivals and departures in order to reduce a delay function of all the flights, using a more realistic representation of the airport capacity, i.e. the capacity envelope. Under the assumption of piecewise linear convex capacity envelopes and of the exact interpolation of all the Pareto‐optimal operational points, we show that the problem can be formulated as a linear programming model. For general airport capacity envelopes, we propose a dynamic programming formulation with a corresponding backward solution algorithm, which is robust, easy to implement and has a linear computational complexity. The algorithm performances are evaluated on different realistic scenarios, and the optimal solutions are compared with those computed by a greedy algorithm, which can be seen as an approximation of the current decision procedures. The percentage deviation of the cost of these two solutions ranges from 3.98 to 35.64%
---
paper_title: The Locomotive Routing Problem

paper_content:

Given a schedule of trains, the locomotive planning (or scheduling) problem (LPP) is to determine the minimum cost assignment of locomotive types to trains that satisfies a number of business and operational constraints. Once this is done, the railroad has to determine the sequence of trains to which each locomotive is assigned by unit number so that it can be fueled and serviced as necessary. We refer to this problem as the locomotive routing problem (LRP). The LRP is a very large scale combinatorial optimization problem, and the general version that we consider has previously been unstudied and unsolved in the research literature. In this paper, we develop robust optimization methods to solve the LRP. There are two major sets of constraints that need to be satisfied by each locomotive route: (1) locomotive fueling constraints, which require that every unit visit a fueling station at least once for every F miles of travel, and (2) locomotive servicing constraints, which require that every unit visit a service station at least once for every S miles of travel. The output of the LPP is not directly implementable because the LPP does not consider these fueling and servicing constraints. The LRP considers these constraints, and its output is therefore implementable. We model the LRP by considering alternative fueling and servicing friendly train paths (or strings) between servicing stations on the network. We formulate the LRP as an integer programming problem on a suitably constructed space-time network and show that this problem is NP-Complete. This integer programming problem has millions of decision variables. We develop a fast aggregation-disaggregation based algorithm to solve the problem within a few minutes of computational time to near optimality. Finally, we present computational results and extensive case studies of our algorithms on real data provided by a major Class I U.S. railroad.
---
paper_title: Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

paper_content:

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.
---
paper_title: A transgenic algorithm for the Vehicle Routing Problem with Time Windows

paper_content:

In this paper, we present a transgenic computer algorithm based on the transformation mechanism of horizontal gene transfer to solve the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is the problem of minimising transportation costs while satisfying some restrictions as the time, vehicle capacity and the demand of each client. Horizontal gene artificial transfer is a form of genetic engineering. The transgenic algorithm is considered as a horizontal gene transfer algorithm, a meta-heuristics algorithm, or a bio-inspired algorithm based on horizontal gene transfer and symbiogenesis. The transgenic algorithm uses a data-mining technique (clustering) to group similar characteristics of the VRPTW instance to obtain the initial population (one VRPTW individual), a genetic transfer phase inspired by the transference of genetic codes of a bacterial gene (depot) contained in mechanisms for the horizontal gene transfer, and an intelligent mutation operator inspired by symbiogenesis called symbion operator. The transgenic algorithm (lateral gene transfer algorithm, or horizontal gene transfer algorithm) involves deliberate genetic modification rather than evolutionary aspects. We demonstrate that it is possible to deploy a transgenic algorithm based on horizontal gene transfer to solve (in fewer generations and less time) the VRPTW than the results of the genetic algorithm.
---
paper_title: School bus routing using genetic algorithms

paper_content:

ABSTRACT The school bus routing problem involves transporting students from predefined locations to the schoolusing a fleet of school buses with varying capacity. The objective is to minimize the fleet size in addition tominimizing the distance traveled by the buses and the travel time of the students. As the school bus routingproblem belongs to the NP-complete class of problems, search strategies based on heuristic methods are mostpromising for problems in this class. GENROUTER is a system that uses genetic algorithms, an adaptiveheuristic search strategy, for routing school buses. The GENROUTER system was used to route school buses fortwo school districts. The routes obtained by GENROUTER system were superior to those obtained by the Cl-lOOSE school bus routing system and the current routes in use by the two school districts. 1. INTRODUCTION Genetic algorithms are adaptive heuristic search strategies based on the principles of population genetics.They have been used to solve a number of combinatorially explosive problems with successful results. Some of
---
paper_title: Column generation based heuristics for a generalized location routing problem with profits arising in space exploration

paper_content:

The generalized location routing problem with profits is a new routing problem class that combines the vehicle routing problem with profits, depot or base selection, and the notion of strategies and route tactics to be employed at selected bases. The problem simultaneously determines base locations, strategies to use at the bases, sites to visit, and routes to carry out the visits, to maximize the sum of profits that can be obtained by visiting sites, under resource consumption constraints. The problem arises in exploration of planetary bodies where strategies correspond to different technologies. A description of the generalized location routing problem with profits and its mathematical formulation as an integer program are provided. Two solution methodologies to solve the problem – branch-and-price and a three-phase heuristic method combined with a generalized randomized adaptive search procedure – are proposed. Numerical experiments for the two solution methodologies are carried out. Their performance in terms of computation time and optimality gap are analyzed and compared to establish the problem characteristics, indicating which method is more advantageous.
---
paper_title: Heuristic methods for vehicle routing problem with time windows

paper_content:

Abstract This paper documents our investigation into various heuristic methods to solve the vehicle routing problem with time windows (VRPTW) to near optimal solutions. The objective of the VRPTW is to serve a number of customers within predefined time windows at minimum cost (in terms of distance travelled), without violating the capacity and total trip time constraints for each vehicle. Combinatorial optimisation problems of this kind are non-polynomial-hard (NP-hard) and are best solved by heuristics. The heuristics we are exploring here are mainly third-generation artificial intelligent (AI) algorithms, namely simulated annealing (SA), Tabu search (TS) and genetic algorithm (GA). Based on the original SA theory proposed by Kirkpatrick and the work by Thangiah, we update the cooling scheme and develop a fast and efficient SA heuristic. One of the variants of Glover's TS, strict Tabu, is evaluated and first used for VRPTW, with the help of both recency and frequency measures. Our GA implementation, unlike Thangiah's genetic sectoring heuristic, uses intuitive integer string representation and incorporates several new crossover operations and other advanced techniques such as hybrid hill-climbing and adaptive mutation scheme. We applied each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems. This paper is also among the first to document the implementation of all the three advanced AI methods for VRPTW, together with their comprehensive results.
---
paper_title: Parallel heterogeneous genetic algorithms for continuous optimization

paper_content:

In this paper we address the physical parallelization of a very efficient genetic algorithm (GA) known as gradual distributed real-coded GA (GD-RCGA). This search model naturally provides a set of eight subpopulations residing in a cube topology having two faces for promoting exploration and exploitation. The resulting technique has been shown to yield very accurate results in continuous optimization by using crossover operators tuned to explore and exploit the solutions inside each subpopulation. Here, we encompass the actual parallelization of the technique, and get deeper into the importance of running a synchronous versus an asynchronous version of the basic GD-RCGA model. We also present the evaluation of the parallel execution of GD-RCGA over two local area networks, a Fast-Ethernet network and a Myrinet network. Our results indicate that the GD-RCGA model maintains a very high level of accuracy for continuous optimization when run in parallel, and we also demonstrate the relative advantages of each algorithm version over the two networks. Finally, we show that the async parallelization scales better than the sync one, what suggests future research lines for WAN execution and new models of search based on the original two-faced cube.
---
paper_title: A metaheuristic for solving large instances of the School Bus Routing Problem

paper_content:

The school bus routing problem discussed in this paper, is similar to the standard vehicle routing problem, but has several interesting additional features. In the standard VRP all stops to visit are given. In our school bus routing problem, we assume that a set of potential stops is given, as well as a set of students that can walk to one or more stops. The school buses used to pick up the students and transport them to their schools have a finite capacity. The goal of this routing problem is to select a subset of stops that will actually be visited by the buses, determine which stop each student should walk to and develop a set of tours that minimize the total distance travelled by all buses. The focus in this paper lies on understanding the problem in its simple form and on building a powerful meta-heuristic to solve large instances quickly. Our solution method starts with a GRASP-like savings algorithm, after which a Variable Neigbourhood Search algorithm is used to improve the initial solution. A modified version of the well-known transportation problem helps the meta-heuristic to quickly assign students to stops.
---
paper_title: A GRASP for the Vehicle Routing Problem with Time Windows

paper_content:

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window constraints. A secondary objective is to minimize the total distance traveled. Each node requires a predetermined amount of service in the form of pickups and deliveries. The fleet is homogeneous and is located at a common depot. Vehicle capacity is finite and split service is not permitted. A greedy randomized adaptive search procedure (GRASP) is used to obtain feasible solutions. Results are reported for standard 100 node data sets as well as for a number of real-world problems with up to 417 customers. The findings indicate that, in general, the proposed procedure outperforms current techniques and requires only a small fraction of the time taken by exact methods. To gauge the quality of the solutions, three different lower bounding heuristics were developed. The first considers the “bin packing” aspect of the problem with regard to vehicle capacity; the second is based on the maximum clique associated with the customers' incompatibility graph; the third independently exploits the time window constraints. Using these heuristics, it is empirically demonstrated that the optimum is found in almost all cases involving balanced service and tight capacity constraints and a significant proportion of the remainder. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: Research on Improved Hybrid Particle Swarm Optimization for Vehicle Routing Problem with Time Windows

paper_content:

Vehicle routing problem with time window (VRPTW) is a very important combinatorial optimization and nonlinear programming problem and it has important practical value in the field of transportation, distribution and logistics. Traditional intelligent optimization algorithms have the common defects of early convergence and easily falling into local optimal solution in solving VRPTW. An improved hybrid particle swarm optimization (IHPSO) has been presented in this paper for the solution to the VRPTW. Population entropy is introduced to ensure the diversities of the solution. Some post-optimization procedures, such 2-opt, 1-1 opt and 1-0 opt, are adopted to optimize the inner or router route and modify illegal solutions. The advantage of the proposed algorithm is proved by the simulation based on Matlab language. The results shows that IHPSO can be dramatically increase the probability of the finding the optimal solution as well as shorted the searching time. It is a feasible and effective algorithm for VRPTW.
---
paper_title: A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows

paper_content:

This paper describes a tabu search heuristic for the vehicle routing problem with soft time windows. In this problem, lateness at customer locations is allowed although a penalty is incurred and added to the objective value. By adding large penalty values, the vehicle routing problem with hard time windows can be addressed as well. In the tabu search, a neighborhood of the current solution is created through an exchange procedure that swaps sequences of consecutive customers (or segments) between two routes. The tabu search also exploits an adaptive memory that contains the routes of the best previously visited solutions. New starting points for the tabu search are produced through a combination of routes taken from different solutions found in this memory. Many best-known solutions are reported on classical test problems.
---
paper_title: Two evolutionary metaheuristics for the vehicle routing problem with time windows

paper_content:

AbstractThe vehicle routing problem with time windows (VRPTW) is an extension of the well-known vehicle routing problem with a central depot. The objective is to design an optimal set of routes that services all customers and satisfies the given constraints, especially the time window constraints. The objective function considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance minimization (secondary criterion). In this paper, two evolution strategies for solving the VRPTW are proposed. The evolution strategies were tested on 58 problems from the literature with sizes varying from 100 to 417 customers and 2 to 54 vehicles. The generated new best known solutions indicate that evolution strategies are effective in reducing both the number of vehicles and the total travel distance
---
paper_title: The Vehicle Routing Problem with Time Windows - Part II: Genetic Search

paper_content:

This paper is the second part of a work on the application of new search techniques for the vehicle routing problem with time windows. It describes GENEROUS, the GENEtic ROUting System, which is based on the natural evolution paradigm. Under this paradigm, a population of solutions evolves from one generation to the next by “mating” parent solutions to form new offspring solutions that exhibit characteristics inherited from their parents. For this vehicle routing application, a specialized methodology is devised for merging two vehicle routing solutions into a single solution that is likely to be feasible with respect to the time window constraints. Computational results on a standard set of test problems are reported, and comparisons are provided with other heuristics.
---
paper_title: Solving train formation problem using simulated annealing algorithm in a simplex framework

paper_content:

SUMMARY ::: The train formation plan (TFP) determines the train services and their frequencies and assigns the demands. The TFP models are often formulated as a capacitated service network design problem, and the optimal solution is normally difficult to find. In this paper, a hybrid algorithm of the Simplex method and simulated annealing is proposed for the TFP problem. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method evaluates, selects, and implements the moves. In the proposed algorithm, the neighborhood structure is based on the pivoting rules of the Simplex method that provides an efficient method to reach the neighbors of the current solution. A state-of-the-art method is applied for parameters tuning by using the design of experiments approach. To evaluate the proposed model and the solution method, 25 test problems have been simulated and solved. The results show the efficiency and the effectiveness of the proposed approach. The proposed approach is implemented to develop the TFP in the Iranian railway as a case study. It is possible to save significant time and cost through solving the TFP problem by using the proposed algorithm and developing the efficient TFP plan in the railway networks. Copyright © 2012 John Wiley & Sons, Ltd.
---
paper_title: Vehicle Routing with Time Windows

paper_content:

In vehicle routing problems with time windows, a fixed fleet of vehicles of limited capacity is available at a depot to serve a set of clients with given demands. Each client must be visited within a given time window. We describe a branch-and-bound method that minimizes the total route length, and present some computational results.
---
paper_title: Population pre-selection operators used for generating a non-random initial population to solve vehicle routing problem with time windows

paper_content:

In this paper, we propose two population pre-selection operators to be improved by the k-means algorithm (clustering) and neighborhood techniques in the determination of the initial population (nonrandom population) used in the evolutionary and genetic algorithms to solve the vehicle routing problem with time windows (VRPTW). The results provide individual or group chromosomes in the initial population that is close to the optimal in VRPTW instances.
---
paper_title: Rural School Vehicle Routing Problem

paper_content:

The school bus routing problem traditionally has been defined in an urban context. However, because of the unique attributes of the problem in rural areas, traditional heuristic methods for solving the problem may produce impractical results. In many cases, these characteristics also provide the opportunity to investigate what size and mix of vehicles, whether large or small buses, conforming vans, or other modes, are most efficient. In addition, these vehicles may be further differentiated by the presence of equipment for transporting students with special needs. To address this situation, a mathematical model of the problem was constructed and a new heuristic was developed. This heuristic consists of two parts: constructing the initial route and then improving it by using a fixed tenure tabu search algorithm. This rural routing heuristic, in addition to several existing ones, is then applied to a randomly generated school district with rural characteristics. For the relevant measure, a function of stude...
---
paper_title: Optimization of railway operations using neural networks

paper_content:

Railroad operations involve complex switching and classification decisions that must be made in short periods of time. Optimization with respect to these decisions can be quite difficult due to the discrete and non-linear characteristics of the problem. The train formation plan is one of the important elements of railroad system operations. While mathematical programming formulations and algorithms are available for solving the train formation problem, the CPU time required for their convergence is excessive. At the same time, shorter decision intervals are becoming necessary given the highly competitive operating climates of the railroad industry. The field of Artificial Intelligence (AI) offers promising alternatives to conventional optimization approaches. In this paper, neural networks (an empirically-based AI approach) are examined for obtaining good solutions in short time periods for the train formation problem (TFP). Following an overview, and formulation of railroad operations, a neural network formulation and solution to the problem are presented. First a training process for neural network development is conducted followed by a testing process that indicates that the neural network model will probably be both sufficiently fast, and accurate, in producing train formation plans.
---
paper_title: Passenger and pilot risk minimization in offshore helicopter transportation

paper_content:

In the offshore petroleum industry, employees are transported to and from the offshore installations by helicopter, which represents a major risk. This paper analyzes how to improve transportation safety by solving the helicopter routing problem with a risk objective expressed in terms of expected number of fatalities. A mathematical model is proposed and a tabu search heuristic is applied to this problem. Three routing policies are considered: a direct routing policy, a Hamiltonian routing policy, and a general routing policy. Extensive computational experiments are conducted on instances derived from real data in order to assess and compare these policies under a travel time, a passenger risk and a combined passenger and pilot risk objective. Several management insights can be derived from this study. In particular, our results show that passenger transportation risk can be reduced by increasing travel time at the expense of pilot risk. This can be achieved through a reduction of the average number of passengers onboard by applying either a Hamiltonian or a general routing policy. Our methodology can also be used to derive an equitable distribution of risk between passengers and pilots, considering that pilots fly much more frequently than passengers.
---
paper_title: Low cost parallel solutions for the VRPTW optimization problem

paper_content:

In the paper a parallelizable system based on simulated annealing to solve vehicle routing problem with time window (VRPTW) problems is described. The system consists of two optimization phases: a global one, and local one, both based on simulated annealing and parallizable. For the first phase different parallelization strategies are presented and evaluated. The importance of the co-operation among processors has been made clear: the communication of partial solutions improves the efficiency of optimal solution's search. Two algorithms, a synchronous one and an asynchronous one, stand out due to their good average behaviour related to the quality of solutions found, and due to their stability when augmenting the number of processors. The second phase has shown to be a great complement of the global search that permits to obtain a very fast and practical, low cost parallel system. This system has been able to reach the optimal solution published for the Solomon's benchmark in an 85% of the problems, and more important, the averages of any set of random executions are less than 5% worse than the best published.
---
paper_title: A GENETIC ALGORITHM APPROACH FOR SOLVING THE TRAIN FORMATION PROBLEM

paper_content:

The train formation plan is one of the most important elements of railroad system operations. Although mathematical programming formulations and algorithms are available for solving the train formation problem (TFP), the computational time required for their convergence is usually excessive. At the same time, shorter decision intervals are becoming necessary given the highly competitive operating climates of the railroad industry. Thus, new techniques are needed for generating efficient solutions for the TFP. In this study, the authors present the development of a genetic algorithm (GA) as a possible technique for this problem. The calibration and validation of the GA model are carried out for three different complexity levels of objective functions. It is found that the optimal solutions can be found for all the different formulations while consuming only a small amount of computation time.
---
paper_title: A unified tabu search heuristic for vehicle routing problems with time windows

paper_content:

This paper presents a unified tabu search heuristic for the vehicle routing problem with time windows and for two important generalizations: the periodic and the multi-depot vehicle routing problems with time windows. The major benefits of the approach are its speed, simplicity and flexibility. The performance of the heuristic is assessed by comparing it to alternative methods on benchmark instances of the vehicle routing problem with time windows. Computational experiments are also reported on new randomly generated instances for each of the two generalizations.
---
paper_title: A vertical transfer algorithm for the School Bus Routing Problem

paper_content:

In this paper is a solution to the School Bus Routing Problem by the application of a bio-inspired algorithm in the vertical transfer of genetic material to offspring or the inheritance of genes by subsequent generations. The vertical transfer algorithm or Genetic algorithm uses the clusterization population pre-selection operator, tournament selection, crossover-k operator and an intelligent mutation operator called mutation-S. The use of the bio-inspired algorithm to solve SBRP instances show good results about Total Bus Travel Distance and the Number of Buses with the Routes.
---
paper_title: A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows

paper_content:

This paper presents a hybrid genetic algorithm to solve a multi-depot homogenous locomotive assignment problem with time windows. The locomotive assignment problem is to assign a set of homogeneous locomotives locating in a set of dispersed depots to a set of pre-schedules trains that are supposed to be serviced in pre-specified hard/soft time windows. A mathematical model is presented, using vehicle routing problem with time windows (VRPTW) for formulation of the problem. A cluster-first, route-second approach is used to inform the multi-depot locomotive assignment to a set of single depot problems and after that we solve each problem independently. Each single depot problem is solved heuristically by a hybrid genetic algorithm that in which Push Forward Insertion Heuristic (PFIH) is used to determine the initial solution and @l-interchange mechanism is used for neighborhood search and improving method. A medium sized numerical example with different scenarios is presented and examined to more clarification of the approach as well as to check capabilities of the model and algorithm. Also some of the results are compared with the solutions produced by branch & bound technique to determine validity and quality of the model. The experiments with a set of 15 completely random generated instance problems indicate that this algorithm is efficient and solves the problem in a polynomial time.
---
paper_title: An Extended Branch-and-Bound Method for Locomotive Assignment

paper_content:

This paper considers the locomotive assignment problem encountered during the planning of the operations of a freight railroad, which consists of providing sufficient motive power to pull a set of scheduled trains at minimum cost while satisfying locomotive availability and maintenance requirements. In 1997, Ziarati et al. proposed for this problem a heuristic branch-and-price approach that relies on a simple depth-first search strategy without backtracking. In this paper, we present an efficient backtracking mechanism that can be added to this heuristic branch-and-price approach. To do so, we propose and evaluate different branching methods that impose multiple decisions on locomotive routes at each branching node, including one decision that forbids one such route. Finally, we introduce different ways of computing an estimate of the best integer solution value that can be obtained from a branch-and-bound node. These estimates can be used to guide the backtracking process of a two-phase search strategy.
---
paper_title: On the tour planning problem

paper_content:

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
---
paper_title: A hybrid genetic algorithm for train sequencing in the Korean railway

paper_content:

This article addresses the train-sequencing problem encountered in the Korean railway. It first presents a mixed integer programming model for the problem, in which the mileage must be balanced for each train route, while various field constraints must be satisfied, including overnight stay capacity and maintenance allocation restrictions. Then, it proposes a hybrid genetic algorithm as a solution approach to the problem. The proposed algorithm utilizes a modified elite group technique along with two heuristic procedures based on the mixed integer programming model. Finally, the proposed solution approach is tested with real-world data from the Korean railway. Numerical experiments under different conditions indicate that the proposed solution approach to the train-sequencing problem is promising.
---
paper_title: A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem

paper_content:

We consider a distribution problem in which a product has to be shipped from a supplier to several retailers over a given time horizon. Each retailer defines a maximum inventory level. The supplier monitors the inventory of each retailer and determines its replenishment policy, guaranteeing that no stockout occurs at the retailer (vendor-managed inventory policy). Every time a retailer is visited, the quantity delivered by the supplier is such that the maximum inventory level is reached (deterministic order-up-to level policy). Shipments from the supplier to the retailers are performed by a vehicle of given capacity. The problem is to determine for each discrete time instant the quantity to ship to each retailer and the vehicle route. We present a mixed-integer linear programming model and derive new additional valid inequalities used to strengthen the linear relaxation of the model. We implement a branch-and-cut algorithm to solve the model optimally. We then compare the optimal solution of the problem with the optimal solution of two problems obtained by relaxing in different ways the deterministic order-up-to level policy. Computational results are presented on a set of randomly generated problem instances.
---
paper_title: Formulations and Branch-and-Cut Algorithms for Multi-Vehicle Production and Inventory Routing Problems

paper_content:

The inventory routing problem (IRP) and the production routing problem (PRP) are two difficult problems arising in the planning of integrated supply chains. These problems are solved in an attempt to jointly optimize production, inventory, distribution, and routing decisions. Although several studies have proposed exact algorithms to solve the single-vehicle problems, the multivehicle aspect is often neglected because of its complexity. We introduce multivehicle PRP and IRP formulations, with and without a vehicle index, to solve the problems under both the maximum level (ML) and order-up-to level (OU) inventory replenishment policies. The vehicle index formulations are further improved using symmetry breaking constraints; the nonvehicle index formulations are strengthened by several cuts. A heuristic based on an adaptive large neighborhood search technique is also developed to determine initial solutions, and branch-and-cut algorithms are proposed to solve the different formulations. The results show that the vehicle index formulations are superior in finding optimal solutions, whereas the nonvehicle index formulations are generally better at providing good lower bounds on larger instances. IRP and PRP instances with up to 35 customers, three periods, and three vehicles can be solved to optimality within two hours for the ML policy. By using parallel computing, the algorithms could solve the instances for the same policy with up to 45 and 50 customers, three periods, and three vehicles for the IRP and PRP, respectively. For the more difficult IRP (PRP) under the OU policy, the algorithms could handle instances with up to 30 customers, three (six) periods, and three vehicles on a single core machine, and up to 45 (35) customers, three (six) periods, and three vehicles on a multicore machine.
---
paper_title: Metaheuristics for Tourist Trip Planning

paper_content:

The aim of this paper is to present an overview of metaheuristics used in tourism and to introduce Skewed VNS to solve the team orienteering problem (TOP). Selecting the most interesting points of interest and designing a personalised tourist trip, can be modelled as a TOP with time windows (TOPTW). Guided local search (GLS) and variable neighbourhood search (VNS) are applied to efficiently solve the TOP. Iterated local search (ILS) is implemented to solve the TOPTW. The GLS and VNS algorithms are compared with the best known heuristics and applied on large problem sets. The obtained results are almost of the same quality as the results of these heuristics but the computational time is reduced significantly. For some of the problems VNS calculates new best solutions. The results of the ILS algorithm, applied to large problem sets, have an average gap with the optimal solution of only 2.7%, with much less computational effort.
---
paper_title: Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery

paper_content:

In this paper we observe the extension of the vehicle routing problem (VRP) in fuel delivery that includes petrol stations inventory management and which can be classified as the Inventory Routing Problem (IRP) in fuel delivery. The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. We developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies with each petrol station and each fuel type. The stochastic VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic ''compartment transfer'' (CT) heuristic. For three different scale problems, with different vehicle types, the developed VNS heuristic outperforms the deterministic CT heuristic. Also, for the smallest scale problem instances, the developed VNS was capable of obtaining the near optimal and optimal solutions (the MILP model was able to solve only the smallest scale problem instances).
---
paper_title: Bi-Objective Bus Routing: An Application to School Buses in Rural Areas

paper_content:

The min-max vehicle routing problem VRP is a variant of the classical VRP in which the objective is to minimize the duration of the longest route. Examination of the VRP literature indicates that the min-max VRP has received less attention than other variants have over the years. However, the problem has important practical applications, such as those related to routing school buses. In this setting, in addition to the min-max criterion imposed on the time it takes to complete the longest route, school districts are concerned with the minimization of the total distance traveled, which is the objective of the classical VRP. Hence, the problem is formulated as a bi-objective optimization model that trades off service i.e., the minimization of the longest route and operational cost i.e., the minimization of the total distance traveled. We develop a solution procedure for this problem by applying tabu search within the framework of Multiobjective Adaptive Memory Programming and compare it to an implementation of the Non-dominated Sorting Genetic Algorithm---a well-known approach to multiobjective optimization. We also assess the merit of the solution method by comparing our approximations with solution frontiers obtained with an e-constraint implementation.
---
paper_title: A branch-and-price algorithm for an integrated production and inventory routing problem

paper_content:

With globalization, the need to better integrate production and distribution decisions has become ever more pressing for manufacturers trying to streamline their supply chain. This paper investigates a previously developed mixed-integer programming (MIP) model aimed at minimizing production, inventory, and delivery costs across the various stages of the system. The problem being modeled includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of homogeneous vehicles. Demand can be satisfied from either inventory held at a customer site or from daily product distribution. Whether a customer is visited on a particular day is determined by an implicit tradeoff between inventory and distribution costs. Once the decision is made, a vehicle routing problem must be solved for those customers who are scheduled for a delivery. A hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework is developed to solve the underlying MIP. The approach takes advantage of the efficiency of heuristics and the precision of branch and price. Implementation required devising a new branching strategy to accommodate the unique degeneracy characteristics of the master problem, and a new procedure for handling symmetry. A novel column generation heuristic and a rounding heuristic were also implemented to improve algorithmic efficiency. Computational testing on standard data sets showed that the hybrid scheme can solve instances with up to 50 customers and 8 time periods within 1h. This level of performance could not be matched by either CPLEX or standard branch and price alone.
---
paper_title: A memetic algorithm for the team orienteering problem

paper_content:

The Team Orienteering Problem (TOP) is a generalization of the Orienteering Problem (OP). A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid Genetic Algorithm (GA) using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and Local Search techniques for mutation. We have called this hybrid method a Memetic Algorithm (MA) for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 11 instances.
---
paper_title: The exact solution of several classes of inventory-routing problems

paper_content:

In order to be competitive companies need to take advantage of synergistic interactions between different decision areas. Two of these are related to the distribution and inventory management processes. Inventory-Routing Problems (IRPs) arise when inventory and routing decisions must be made simultaneously, which yields a difficult combinatorial optimization problem. In this paper, we propose a branch-and-cut algorithm for the exact solution of several classes of IRPs. Specifically, we solve the multi-vehicle IRP with a homogeneous and a heterogeneous fleet, the IRP with transshipment options, and the IRP with added consistency features. We perform an extensive computational analysis on benchmark instances.
---
paper_title: A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem

paper_content:

We consider a maritime inventory routing problem in the liquefied natural gas (LNG) business, called the LNG inventory routing problem (LNG-IRP). Here, an actor is responsible for the routing of the fleet of special purpose ships, and the inventories both at the liquefaction plants and the regasification terminals. Compared to many other maritime inventory routing problems, the LNG-IRP includes some complicating aspects such as (1) a constant rate of the cargo evaporates each day and is used as fuel during transportation; (2) variable production and consumption of LNG, and (3) a variable number of tanks unloaded at the regasification terminals. The problem is solved by a branch-and-price method. In the column generation approach, the master problem handles the inventory management and the port capacity constraints, while the subproblems generate the ship route columns. Different accelerating strategies are implemented. The proposed method is tested on instances inspired from real-world problems faced by a major energy company.
---
paper_title: An exact algorithm for team orienteering problems

paper_content:

Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100 customers.
---
paper_title: A metaheuristic for the school bus routing problem with bus stop selection

paper_content:

Existing literature on routing of school buses has focused mainly on building intricate models that attempt to capture as many real-life constraints and objectives as possible. In contrast, the focus of this paper is on understanding the joint problem of bus route generation and bus stop selection – two important sub-problems – in its most basic form. To this end, this paper defines the school bus routing problem (SBRP) as a variant of the vehicle routing problem in which three simultaneous decisions have to be made: (1) determine the set of stops to visit, (2) determine for each student which stop (s)he should walk to, and (3) determine routes that lie along the chosen stops, so that the total traveled distance is minimized. An MIP model of this basic problem is developed.
---
paper_title: Multiobjective Evolutionary Algorithms in Aeronautical and Aerospace Engineering

paper_content:

Nowadays, the solution of multiobjective optimization problems in aeronautical and aerospace engineering has become a standard practice. These two fields offer highly complex search spaces with different sources of difficulty, which are amenable to the use of alternative search techniques such as metaheuristics, since they require little domain information to operate. From the several metaheuristics available, multiobjective evolutionary algorithms (MOEAs) have become particularly popular, mainly because of their availability, ease of use, and flexibility. This paper presents a taxonomy and a comprehensive review of applications of MOEAs in aeronautical and aerospace design problems. The review includes both the characteristics of the specific MOEA adopted in each case, as well as the features of the problems being solved with them. The advantages and disadvantages of each type of approach are also briefly addressed. We also provide a set of general guidelines for using and designing MOEAs for aeronautical and aerospace engineering problems. In the final part of the paper, we provide some potential paths for future research, which we consider promising within this area.
---
paper_title: Solving Real-Life Railroad Blocking Problems

paper_content:

Each major US railroad ships millions of cars over its network annually. To reduce the intermediate handlings of shipments as they travel over the railroad network, a set of shipments is classified (or grouped together) at a railroad yard to create a block. The railroad blocking problem is to identify this classification plan for all shipments at all yards in the network to minimize the total shipment cost, i.e., to create a blocking plan. The railroad blocking problem is a very large-scale, multicommodity, flow-network-design and routing problem with billions of decision variables. Its size and mathematical difficulty preclude solving it using any commercial software package. We developed an algorithm using an emerging technique known as very large-scale neighborhood (VLSN) search that is able to solve the problem to near optimality using one to two hours of computer time on a standard workstation computer. This algorithm can also handle a variety of practical and business constraints that are necessary for implementing a solution. When we applied this algorithm to the data that several railroads provided us, the computational results were excellent. Three Class I railroad companies (a Class I railroad, as defined by the Association of American Railroads, has an operating revenue exceeding $319.3 million) in the United States---CSX Transportation, Norfolk Southern Corporation, and Burlington Northern and Santa Fe Railway---used it in developing their operating plans. Two US Class I railroads have also licensed it for regular use in developing their operating plans, and other railroads are showing considerable interest. We expect this algorithm to become an industry standard for freight railroads worldwide. In this paper, we outline our algorithm, show the computational results we received using real data, and describe areas for future research.
---
paper_title: A Simulated Annealing Heuristic for the Truck and Trailer Routing Problem with Time Windows

paper_content:

European firms have been using a combination of trucks and trailers in the delivery/collection of food products for years. Thus, some previous studies had been devoted to improving the efficiency of the resulting truck and trailer routing problem (TTRP). Since time window constraints are present in many real-world routing applications, in this study, we introduce the truck and trailer routing problem with time windows (TTRPTW) to bring the TTRP model closer to the reality. A simulated annealing (SA) heuristic is proposed for solving the TTRPTW. Two computational experiments are conducted to test the performance of the proposed SA heuristic. The results indicate that the proposed SA heuristic is capable of consistently producing quality solutions to the TTRPTW within a reasonable time.
---
paper_title: A genetic algorithm for railway scheduling with environmental considerations

paper_content:

Abstract A genetic algorithm is a randomized optimization technique that draws its inspiration from the biological sciences. Specifically, it uses the idea that genetics determines the evolution of any species in the natural world. Integer strings are used to encode an optimization problem and these strings are subject to combinatorial operations called reproduction, crossover and mutation, which improve these strings and cause them to ‘evolve’ to an optimal or nearly optimal solution. In this paper, the general machinations of genetic algorithms are described and a performance-enhanced algorithm is proposed for solving the important practical problem of railway scheduling. The problem under consideration involves moving a number of trains carrying mineral deposits across a long haul railway line with both single and double tracks in either direction. Collisions can only be avoided in sections of the line with double tracks. Constraints reflecting practical requirements to reduce environmental impacts from mineral transport, such as avoidance of loaded trains traversing populated areas during certain time slots, have to be satisfied. This is an NP-hard problem, which usually requires enumerative, as opposed to constructive, algorithms. For this reason, an ‘educated’ random search procedure like the genetic algorithm is an alternative and effective technique. The genetic algorithm is given difficult test problems to solve and the algorithm was able to generate feasible solutions in all cases.
---
paper_title: Freight Routing and Scheduling at CSX Transportation

paper_content:

Two of a railroad's fundamental tactical operations are routing shipments along its rails and scheduling trains necessary to ser vice the routes. The computer-aided routing and scheduling system (CARS) bridges the gap between these day-to-day oper ations and strategic planning. By investigating low-cost routes and schedules in a controlled environment under various cost scenarios, CSX Transportation's strategic planners can better ac count for these tactical operations in their long-range policies. CSX Transportation (CSXT) is one of the largest railroads in the world. Its rail network spans over 20,000 miles in 19 states and Canada (Figure 1). Its 35,000 employees operate over 1,500 trains pull ing over 200,000 freight cars per day. Each year CSXT ships over two million carloads of coal and one billion bushels of grain. In just its first decade, CSXT has become the largest shipper of goods in the United States.
---
paper_title: Simulated annealing for the multi-objective aircrew rostering problem

paper_content:

The aircrew rostering problem entails the assignment of crew members to planned rotations. Airline companies have the monthly task of constructing personalized monthly schedules (rosters). The paper attempts to solve the aircrew rostering problem as a multi-objective optimization problem, thus constructing personalized monthly schedules on the basis of several criteria. The proposed algorithm to solve the aircrew rostering problem contains two steps. The first step uses the 'pilot-by-pilot' heuristic algorithm to generate an initial feasible solution. The second step uses the simulated annealing technique for multi-objective optimization problems to improve the solution obtained in the first step. The paper develops two models to improve the initial solution obtained in the first step. The developed models are tested on a numerical example whose dimensions are characteristic of small- and medium-sized airline carriers. The other examples on which the models are tested are randomly generated. Â©
---
paper_title: A post-improvement procedure for the mixed load school bus routing problem

paper_content:

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.
---
paper_title: A genetic algorithm approach to periodic railway synchronization

paper_content:

We consider the compilation of timetables for periodic served railway networks. The calculation of timetables with minimal waiting time for passengers changing trains is modeled by a periodic network optimization problem. We present a genetic algorithm which is combined with a greedy heuristic and a local improvement procedure.
---
paper_title: Study on intelligent train dispatching

paper_content:

A GA-based train dispatching method is presented. A model for train dispatching on lines with double tracks is established first, the model can optimize train dispatching by adjusting the order and times of train departures from stations, and then the efficiency of the method is demonstrated by simulation of the Guangzhou to Shenzhen high-speed railway.
---
paper_title: A simulated annealing heuristic for the team orienteering problem with time windows

paper_content:

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.
---
paper_title: Solving the truck and trailer routing problem based on a simulated annealing heuristic

paper_content:

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.
---
paper_title: Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

paper_content:

We report about a study of a simulated annealing algorithm for the airline crew pairing problem based on a run-cutting formulation. Computational results are reported for some real-world short- to medium-haul test problems with up to 4600 flights per month. Furthermore we find that run time can be saved and solution quality can be improved by using a problem specific initial solution, by relaxing constraints “as far as possible”, by combining simulated annealing with a problem specific local improvement heuristic and by multiple independent runs.
---
paper_title: A maritime inventory routing problem: Practical approach

paper_content:

Despite of the practicality of the motivation of the inventory routing problem (IRP), there are few successful implementation stories of IRP based decision support systems which utilize optimization algorithms. Besides the fact that the IRP is an extremely challenging optimization problem, simplifications and assumptions made in the definition of typical IRP in the literature make it even more difficult to take advantage of the developed technologies for IRP in practice. This paper introduces a flexible modeling framework for IRP, which can accommodate various practical features. A simple algorithmic framework of an optimization based heuristic method is also proposed. A case study on a practical maritime inventory routing problem (MIRP) shows that the proposed modeling and algorithmic framework is flexible and effective enough to be a choice of model and solution method for practical inventory routing problems.
---
paper_title: Multi-route railroad blocking problem by improved model and ant colony algorithm in real world

paper_content:

In rail freight transportation, general merchandise freight cars may pass through many classification stations on their route from origin to destination. The Railroad Blocking Problem (RBP) is to reclassify inbound traffic from various origins in the classification stations and put them on outbound trains with the same or close destinations, the objective of the RBP is to minimize the total operating costs of delivering all traffic on the railway network while satisfying the resource and capacity constraints at the stations and the priority constraints for shipments. In this paper, we introduce a new mathematic model which can comprehensively describe the blocking strategy and various combinations of multi-route O-D pairs in large scale railway network. Furthermore, we propose an improved Ant Colony (AC) algorithm for RPB, and a computational experiment derived from the real life instances of coal heavy haul rail network in north China is given. Experimental results verified the validation of the model and effectiveness of the algorithm.
---
paper_title: A tabu search method for the truck and trailer routing problem

paper_content:

Abstract A solution construction method and a tabu search improvement heuristic coupled with the deviation concept found in deterministic annealing is developed to solve the truck and trailer routing problem. We test our tabu search method on 21 problems that have been converted from the basic vehicle routing problem. Our construction method always solves a problem (it always finds a feasible solution) and the tabu search improvement heuristic significantly improves an initial solution. Scope and purpose The vehicle routing problem holds a central place in distribution management and logistics, and its practical significance has been well documented in the literature. The truck and trailer routing problem is a variant of the vehicle routing problem to take into account some real-life applications in which fleet of m k trucks and m l trailers ( m k ⩾ m l ) services a set of customers. Some customers can be serviced by a complete vehicle (that is, a truck pulling a trailer) or by a truck alone, whereas others can be serviced only a truck alone. There are three types of routes in a solution to the problem: (1) a pure truck route traveled by a truck alone, (2) a pure vehicle route without any sub-tours traveled by a complete vehicle, and (3) a complete vehicle route consisting of a main tour traveled by a complete vehicle, and one or more sub-tours traveled by a truck alone. A sub-tour begins and finishes at a customer on the main tour where the truck uncouples, parks, and re-couples its pulling trailer and continues to service the remaining customers on the sub-tour. The objective is to minimize the total distance traveled, or total cost incurred by the fleet. The problem is more difficult to solve than the basic vehicle routing problem, but it occurs in many real-life applications. The purpose of this article is to develop a solution method that generates an initial solution and improves the solution using tabu search. The tabu search procedure uses the deviation concept found in deterministic annealing to further improve the initial solution. Our heuristic solves the truck and trailer routing problem efficiently and effectively.
---
paper_title: A GRASP with evolutionary path relinking for the truck and trailer routing problem

paper_content:

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.
---
paper_title: Ants can solve the team orienteering problem

paper_content:

The team orienteering problem (TOP) involves finding a set of paths from the starting point to the ending point such that the total collected reward received from visiting a subset of locations is maximized and the length of each path is restricted by a pre-specified limit. In this paper, an ant colony optimization (ACO) approach is proposed for the team orienteering problem. Four methods, i.e., the sequential, deterministic-concurrent and random-concurrent and simultaneous methods, are proposed to construct candidate solutions in the framework of ACO. We compare these methods according to the results obtained on well-known problems from the literature. Finally, we compare the algorithm with several existing algorithms. The results show that our algorithm is promising.
---
paper_title: The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm

paper_content:

Abstract The problem statement tackled in this paper is concentrated on the school bus routing problem (SBRP) in urban areas. This problem is a variant of the vehicle routing problem where we identify three simultaneous decisions that have to be made: determining the set of stops to visit, for each student which stop he should walk to and the latter case occurs when determining the routes visited with the chosen stops, so that the total traveled distance is minimized. Accordingly, to the Tunisian case study and the difficulty to solve it in a manual manner we resort to metaheuristic approaches. We have developed a hybrid evolutionary computation based on an artificial ant colony with a variable neighborhood local search algorithm. Empirically we demonstrate that our algorithm yields consistently better results.
---
paper_title: A TABU search heuristic for the team orienteering problem

paper_content:

This paper describes a tabu search heuristic for the Team Orienteering Problem (TOP). The TOP is a variant of the well-known Vehicle Routing Problem in which a set of vehicle tours are constructed such that the total collected reward received from visiting a subset of customers is maximized and the length of each vehicle tour is restricted by a pre-specified limit. The tabu search heuristic is embedded in an adaptive memory procedure that alternates between small and large neighborhood stages during the solution improvement phase. Both random and greedy procedures for neighborhood solution generation are employed and infeasible, as well as feasible, solutions are explored in the process. Results from computational experiments conducted on a set of published test problems show that the proposed technique consistently produces high-quality solutions and outperforms other published heuristics tbr the TOP.
---
paper_title: Solving airline crew scheduling problems by branch-and-cut

paper_content:

The crew scheduling problem is one that has been studied almost continually for the past 40 years but all prior approaches have always approximated the problem of finding an optimal schedule for even the smallest of an airline's fleets. The problem is especially important today since costs for flying personnel of major U.S. carriers have grown and now often exceed $1.3 billion a year and are the second largest item next to fuel cost of the total operating cost of major U.S. carriers. Thus even small percentage savings amount to substantial dollar amounts. We present a branch-and-cut approach to solving to proven optimality large set partitioning problems arising within the airline industry. We first provide some background related to this important application and then describe the approach for solving representative problems in this problem class. The branch-and-cut solver generates cutting planes based on the underlying structure of the polytope defined by the convex hull of the feasible integer points and incorporates these cuts into a tree-search algorithm that uses automatic reformulation procedures, heuristics and linear programming technology to assist in the solution. Numerical experiments are reported for a sample of 68 large-scale real-world crew scheduling problems. These problems include both pure set partitioning problems and set partitioning problems with side constraints. These "base constraints" represent contractual labor requirements and have heretofore not been represented explicitly in the construction of crew schedules thus making it impossible to provide any measure of how far the obtained solution was from optimality. An interesting result of obtaining less costly schedules is that the crews themselves are happier with the schedules because they spend more of their duty time flying than waiting on the ground.
---
paper_title: Solving Bus Terminal Location Problem Using Genetic Algorithm

paper_content:

Bus networks design is an important problem in public transportation. The main step to this design, is determining the number of required terminals and their locations. This is an especial type of facility location problem, a large scale combinatorial optimization problem that requires a long time to be solved. The genetic algorithm (GA) is a search and optimization technique which works based on evolutionary principle of natural chromosomes. Specifically, the evolution of chromosomes due to the action of crossover, mutation and natural selection of chromosomes based on Darwin's survival-of-the-fittest principle, are all artificially simulated to constitute a robust search and optimization procedure. In this paper, we first state the problem as a mixed integer programming (MIP) problem. Then we design a new crossover and mutation for bus terminal location problem (BTLP). We tested the different parameters of genetic algorithm (for a sample problem) and obtained the optimal parameters for solving BTLP with numerical try and error.
---
paper_title: H2 and H∞ optimal model reduction using genetic algorithms

paper_content:

Abstract The mathematical modeling of most physical systems, such as aerospace systems, heat processes, telecommunication systems, transmission lines and chemical reactors, results in complex high order models. The complexity of the models imposes a lot of difficulties in analysis, simulation and control designs. Several analytical model reduction techniques have been proposed in literature over the past few decades to reduce these difficulties. However, most of the optimal techniques follow computationally demanding, time consuming, iterative procedures that usually result in non-robustly stable models with poor frequency response resemblance to the original high order model in some frequency ranges. Genetic Algorithm (GA) has proved to be an excellent optimization tool in the past few years. Therefore, the aim of this paper will be to use GA to solve H2 and H∞ norm model reduction problems, and help obtain globally optimized nominal models.
---
paper_title: Solving railroad blocking problem using ant colony optimization algorithm

paper_content:

The railroad blocking problem is one of the most important decision in freight railroads. The objective of this problem is to minimize the costs of delivering all commodities by deciding which inter-terminal blocks to build and specifying the assignment of commodities to these blocks, while observing limits on the number and aggregate volume of the blocks assembled at each terminal. This paper presents a metaheuristic algorithm based on ant colony optimization for solving this problem. To evaluate the efficiency of the proposed algorithm and the quality of solutions, experimental analysis is conducted, using several simulated test problems. The results on the test problems are compared with those of solution generated with CPLEX software. The results show high efficiency and effectiveness of the proposed algorithms. The solution method is applied to build car blocking plan in Islamic Republic of Iran Railways. By applying the presented model, Iran Railways can reduce the operational cost considerably and save the time in shipping the freights as well.
---
paper_title: A genetic algorithm approach to the integrated inventory-distribution problem

paper_content:

We introduce a new genetic algorithm (GA) approach for the integrated inventory distribution problem (IIDP). We present the developed genetic representation and use a randomized version of a previously developed construction heuristic to generate the initial random population. We design suitable crossover and mutation operators for the GA improvement phase. The comparison of results shows the significance of the designed GA over the construction heuristic and demonstrates the capability of reaching solutions within 20% of the optimum on sets of randomly generated test problems.
---
paper_title: Iterated local search for the team orienteering problem with time windows

paper_content:

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.
---
paper_title: Transport Logistics Planning with Service-Level Constraints

paper_content:

In this paper, we study a logistics problem arising in military transport planning. A military organization operates a large fleet of vehicles in a depot to serve the requests of various operational units. Each request has a fixed start and end time, and is served by a prescribed number of vehicles. We address the following two problems: (1) how many vehicles are at least needed to meet a given service level of requests; and (2) suppose we allow each request to shift its start time by a constant duration, call all the requests be met? A Niche genetic algorithm, together with a hybridized variant, are applied to the problem.
---
paper_title: Randomized Local Search for Real-Life Inventory Routing

paper_content:

In this paper, a new practical solution approach based on randomized local search is presented for tackling a real-life inventory routing problem. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories: based on consumption forecasts, the vendor organizes delivery routes. Our model takes into account pickups, time windows, drivers' safety regulations, orders, and many other real-life constraints. This generalization of the vehicle-routing problem was often handled in two stages in the past: inventory first, routing second. On the contrary, a characteristic of our local search approach is the absence of decomposition, made possible by a fast volume assignment algorithm. Moreover, thanks to a large variety of randomized neighborhoods, a simple first-improvement descent is used instead of tuned, complex metaheuristics. The problem being solved every day with a rolling horizon, the short-term objective needs to be carefully designed to ensure long-term savings. To achieve this goal, we propose a new surrogate objective function for the short-term model, based on long-term lower bounds. An extensive computational study shows that our solution is effective, efficient, and robust, providing long-term savings exceeding 20% on average, compared to solutions built by expert planners or even a classical urgency-based constructive algorithm. Confirming the promised gains in operations, the resulting decision support system is progressively deployed worldwide.
---
paper_title: An intermodal multicommodity routing problem with scheduled services

paper_content:

We study a multicommodity routing problem faced by an intermodal service operator that uses ground and maritime transportation. Given a planning horizon, a set of commodities to be picked up at their release times and to be delivered not later than their duedates, the problem is to decide on routes for these commodities using trucks and scheduled and capacitated maritime services at minimum cost of transportation and stocking at the seaports. Two mixed integer programming formulations and valid inequalities are proposed for this problem. The results of a computational study to evaluate the strength of the linear programming relaxations and the solution times are reported.
---
paper_title: Solving Real-Life Railroad Blocking Problems

paper_content:

Each major US railroad ships millions of cars over its network annually. To reduce the intermediate handlings of shipments as they travel over the railroad network, a set of shipments is classified (or grouped together) at a railroad yard to create a block. The railroad blocking problem is to identify this classification plan for all shipments at all yards in the network to minimize the total shipment cost, i.e., to create a blocking plan. The railroad blocking problem is a very large-scale, multicommodity, flow-network-design and routing problem with billions of decision variables. Its size and mathematical difficulty preclude solving it using any commercial software package. We developed an algorithm using an emerging technique known as very large-scale neighborhood (VLSN) search that is able to solve the problem to near optimality using one to two hours of computer time on a standard workstation computer. This algorithm can also handle a variety of practical and business constraints that are necessary for implementing a solution. When we applied this algorithm to the data that several railroads provided us, the computational results were excellent. Three Class I railroad companies (a Class I railroad, as defined by the Association of American Railroads, has an operating revenue exceeding $319.3 million) in the United States---CSX Transportation, Norfolk Southern Corporation, and Burlington Northern and Santa Fe Railway---used it in developing their operating plans. Two US Class I railroads have also licensed it for regular use in developing their operating plans, and other railroads are showing considerable interest. We expect this algorithm to become an industry standard for freight railroads worldwide. In this paper, we outline our algorithm, show the computational results we received using real data, and describe areas for future research.
---
paper_title: Intertemporal demand for international tourist air travel

paper_content:

This study investigated dynamic international tourism travel demand by constructing an intertemporal travel choice model. In the model, the utility functions comprise two factors: individuals’ ability to travel and external environmental factors in different years. Individuals are assumed to pursue a maximised aggregated utility, with various discounts on past and future years subject to time and budget constraints. A questionnaire was designed to calibrate and explore individuals’ preferences for international tourism travel from Taiwan. The study collected historic data over the past decade to estimate parameter values for the external environmental factor. The variables, such as travel budget, holiday and vacation days, travel expense and number of travel days are shown to significantly affect individual travel demand. The results support the argument that negative external events, such as an emerging influenza pandemic or economic crisis, have an adverse impact on international travel demand. Moreover...
---
paper_title: The Mobile Tourist Guide: An OR Opportunity

paper_content:

Nowadays, an average tourist plans a vacation using web sites, magazine articles and guidebooks. The inability to modify this holiday plan in real-time motivates the need for a Next Generation Mobile Tourist Guide (MTG). The MTG, a handheld embedded device, is aware of the tourist's preferences, attraction values and trip information. Based on real-time and reliable data, the device can immediately suggest new integrated holiday plans. To develop these holiday plans, additional OR research and very specific decision models are required. In this paper, the Tourist Trip Design Problem (TTDP) is defined as an extension of the Orienteering Problem (OP).
---
paper_title: Optimization Model for Water Distribution System Design

paper_content:

A new methodology is developed for determining the optimal (minium‐cost) design of water distribution systems. The components that can be sized are the pipe network, pumps or pump station, and tanks. In addition, the optimal settings for control and pressure‐reducing valves can be determined. This methodology couples nonlinear programming techniques with existing water distribution simulation models. Previous methodologies have typically simplified the system hydraulics to be able to solve the optimization problem. This new methodology retains the generality of the hydraulic simulation model so that the problem is only limited by the ability of the simulation model rather than the optimization model. The methodology uses a generalized reduced gradient model to solve a problem that is reduced in size and complexity by implicitly solving the conservation of mass and energy equations using the hydraulic simulator and an augmented Lagrangian approach to incorporate pressure head bounds in the objective functi...
---
paper_title: On the tour planning problem

paper_content:

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.
---
paper_title: Network Design Under Budget Constraints With Application To The Railroad Blocking Problem.

paper_content:

Abstract : We develop a column generation based, branch-and-bound algorithm for the directed network budget design problem (BDP), also known as the optimal network design problem, when additional budget constraints are placed on some nodes. Our pricing sub-problems identify new paths for the commodities using a shortest path algorithm. We model the railroad blocking problem (RBP) as a BDP with constraints on the capacities at the nodes and restrictions on the legal paths for each commodity. In RBP, the physical rail network (the railroad terminals and tracks) is already defined. The "blocking network" to be constructed is a virtual network that is overlayed on the physical network. The blocks are virtual "express" arcs which a commodity may take to have uninterrupted service between two terminals that are not necessarily connected by a physical link. Solving RBP requires specifying the blocking network and assigning paths through the blocking network for each commodity. Our solution technique to RBP is unique in constraining the use of resources at the nodes and allowing multiple priority classes for the commodities. Computational results for our algorithm show solutions Within 2.3% of a known lower bound for a real-world RBP instance (with 150 nodes, 1300 commodities, and up to 6,800 candidate arcs after preprocessing) for a large domestic railroad and within 5.5% for randomly generated instances of the same size.
---

Title: A Survey of Transportation Problems

Section 1: Introduction
Description 1: Introduce the general concept of Transportation Problems (TP), the main elements involved, and the objective of the paper.

Section 2: Maritime Transportation Problems
Description 2: Discuss various variants of Maritime Transportation Problems, providing examples and mathematical formulations where applicable.

Section 3: Air Transportation Problems
Description 3: Present different types of Air Transportation Problems along with their mathematical models and objectives.

Section 4: Land Transportation Problems
Description 4: Describe the various Land Transportation Problems, their characteristics, and the mathematical models used to solve them.

Section 5: Rail Transportation Problems
Description 5: Outline the types of Rail Transportation Problems and the specific mathematical models applied to solve them.

Section 6: Space Transportation Problems
Description 6: Detail the variants of Space Transportation Problems and provide explanations of the mathematical formulations for these problems.

Section 7: Pipeline and Cable Transportation Problems
Description 7: Explain the different Pipeline and Cable Transportation Problems, including their specific mathematical models and solutions.

Section 8: Intermodal Transportation Problems
Description 8: Cover the Intermodal Transportation Problems that involve more than one mode of transportation, providing relevant mathematical models.

Section 9: Algorithms to Solve Transportation Problems
Description 9: Summarize various algorithms mentioned in the literature used to solve different Transportation Problems.

Section 10: Conclusions
Description 10: Conclude the paper by summarizing the key points, discussing potential future work, and proposing enhancements to current models and algorithms.