Railway crew capacity planning problem with connectivity of schedules

We study a tactical level crew capacity planning problem in railways which determines the minimum required crew size in a region while both feasibility and connectivity of schedules are maintained. We present alternative mathematical formulations which depend on network representations of the problem. A path-based formulation in the form of a set-covering problem along with a column-and-row generation algorithm is proposed. An arc-based formulation of the problem is solved with a commercial linear programming solver. The computational study illustrates the effect of schedule connectivity on crew capacity decisions and shows that arc-based formulation is a viable approach.     

A GRASP algorithm for the container stowage slot planning problem

This work presents a generalization of the Slot Planning Problem which raises when the liner shipping industry needs to plan the placement of containers within a vessel (stowage planning). State-of-the-art stowage planning relies on a heuristic decomposition where containers are first distributed in clusters along the vessel. For each of those clusters a specific position for each container must be found. Compared to previous studies, we have introduced two new features: the explicit handling of rolled out containers and the inclusion of separations rules for dangerous cargo. We present a novel integer programming formulation and a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the problem. The approach is able to find high-quality solution within 1 s. We also provide comparison with the state-of-the-art on an existing and a new set of benchmark instances.     

Integrated production and intermodal transportation planning in large scale production–distribution-networks

We present a model and solution approach for combining production and intermodal transportation planning in a supply network. A close and detailed integration of both decision fields is missing in the literature so far. The model includes relevant decisions regarding production setups and output volumes of plants, cargo consolidation at intermodal terminals, and capacity bookings for road and rail transports. A Branch-and-Cut method and heuristics are designed for solving the problem. A comprehensive case study for a chemical company identified a 6%-cost saving from the integrated planning. At the same time, companies are successfully supported in establishing eco-friendly distribution processes.     

A comprehensive evacuation planning model and genetic solution algorithm

We consider the problem of evacuating an urban area. Several planning aspects need to be considered in such a scenario, which are usually considered separately. We propose a macroscopic multi-criteria optimization model that includes several such questions simultaneously, and develop a genetic algorithm to solve the problem heuristically. Its applicability is extended by also considering how to aggregate instance data, and how to generate solutions for the original instance starting from a reduced solution. In computational experiments using real-world data, we demonstrate the effectiveness of our approach and compare different levels of data aggregation.     

A matheuristic approach to the air-cargo recovery problem under demand disruption

Air cargo transport is subject to unpredictable changes in expected demand, necessitating adjustments to itinerary planning to recover from such disruptions. We study a flight rescheduling problem to react to cargo demand disruptions in the short run. To increase flexibility, we consider two different cargo assignment policies. We propose a matheuristic approach to solve the problem that provides high-quality solutions in a short computational time, based on column generation in which each subproblem is solved using an ad-hoc heuristic. The approach is tested on demand disruption instances containing up to 75 air cargo orders with different penalty levels. The results show that the proposed method improves profit by 54% over the solution generated by a commercial MIP solver within a 1-h time limit, and by 15% over the solution with the routes fixed as in the original flight planning that only allows cargo to be re-routed. We also show that there exist incremental benefits in the range of 3–5% by allowing cargo for a given order to be transported by various aircraft.     

A column generation based approach for the Train Network Design Optimization problem

This paper investigates the Train Network Design Optimization problem arising from railroad industry which involves the integration of three inter-related decision sub-problems: train routing which is to identify origin, destination and itinerary for individual trains; block-to-train assignment detailing the block movements with trains and swaps between trains; and crew-to-train assignment specifying the crew services for train routes. A column generation based hierarchical approach with two stages is designed: the first stage generates a pool of promising train routes iteratively based on the crew segments by the column generation technique; and the second stage develops an integer linear programming model for the subsequent decisions including train route selection and block-to-train assignment. Numerical experiments with realistic test instances are conducted and the outcome demonstrates the capability of the proposed approach in solving the Train Network Design Optimization problem competently.     

Comparison of solution approaches for the train load planning problem in seaport terminals

In this paper the train load planning problem arising in a seaport container terminal is considered. This problem consists in determining the optimal assignment of containers to wagon slots in order to maximize the train utilization and, at the same time, to minimize unproductive operations in the terminal. Different solution approaches based on a mathematical programming model are compared. The best solution procedure, satisfactory both in terms of quality of the obtained solutions and for the computational times, is identified through extensive experimental tests. This procedure could be included in a planning tool to be used in real seaport terminals.     

Multi-period hub location problems in transportation

Many transport service providers operate on hub-and-spoke network structures. Major operators may have several dedicated hub facilities that are leased for a time horizon rather than being owned or constructed. For a given discrete planning horizon, service providers must decide on the location of the hub ports (i.e. terminals), the period when the lease contract starts, the period when the existing contracts must be terminated and the flow routing over the entire planning horizon so as to minimize the total operational cost. Thus, we propose a mathematical model for a Multi-period Uncapacitated Multiple Allocation Hub Location Problem with Budget Constraint. The proposed model incorporates several features of practice, particularly from maritime and land transport practices. We also propose a meta-heuristic solution algorithm that produces high-quality solutions in a reasonable amount of time. By exploiting the decomposable structure of the model, we extended a Benders decomposition approach by proposing several improvements. Extensive computational experiments confirm the efficiency of the proposed methods and also show its limitations.     

Scenario tree airline fleet planning for demand uncertainty

This paper proposes an innovative multi-period modeling approach to solve the airline fleet planning problem under demand uncertainty. The problem is modeled using a scenario tree approach. The tree is composed of nodes, which represent points of decision in multiple time stages of the planning horizon, and branches, representing demand variation scenarios. The branches link the decision nodes in consequent time stages and compose scenario paths. Fleet decisions are modeled according to these scenario paths, resembling the real-life process in which fleet plans are not defined in a single moment but instead are adjusted according to the demand development. Given that some scenario paths share common decision nodes, decisions among scenarios need to be synchronized. A mixed-integer linear programming model is proposed to determine the ideal fleet composition for each scenario in the tree and to describe this interdependency between scenarios. Considering the probability of a scenario, fleet composition probabilities for each time-period can be determined. Two real-world based case studies are performed to show the validity of the model. Results show that the proposed scenario tree approach can provide flexible multi-period airline fleet plans, which are more robust to future demand scenarios than fleet solutions obtained using the traditional approach of considering a single deterministic demand evolution scenario.     

Aircraft line maintenance scheduling and optimisation

With the advent of new technologies and more modern aircraft, many of the maintenance jobs traditionally scheduled for periodic block checks can now be performed in the ‘‘line maintenance” environment, i.e., during layovers between scheduled flights of an aircraft. This flexibility can be exploited to reduce maintenance costs and improve fleet utilisation of an airline. In this paper we introduce and study the Line Maintenance Scheduling Problem (LMSP). The LMSP assigns jobs to available maintenance opportunities, defined by aircraft routes, and sets the starting time for each job. Its objective is to minimise the deviation from this schedule with respect to given due dates for each task, without exceeding resource capacity at the airports at any moment. We formulate the LMSP as a mixed integer programming problem, and describe and compare two solution approaches for this problem: an integrated exact solution algorithm, which solves job assignment and timetabling simultaneously, and a sequential, heuristic approach. We tested our algorithms on a set of instances inspired on data provided by an industry partner. Our experiments show the applicability of both approaches on realistic settings: the exact approach was able to find the optimal solution for all instances, in less than 10 min on average. Our analysis also shows with an example that line maintenance can be more efficient when capacity is spatially spread, even if the total capacity is reduced.     

Dynamic supply chain network design with capacity planning and multi-period pricing

This paper addresses a new problem in designing and planning a multi-echelon and multi-product supply chain network over a multi-period horizon in which customer zones have price-sensitive demands. Based on price-demand relationships, a generic method is presented to obtain price levels for products and then, a mixed-integer linear programming model is developed. Due to the problem intractability, a simulated annealing algorithm that uses some developed linear relaxation-based heuristics for capacity planning and pricing is presented. Numerical results demonstrate the significance of the model as well as the efficiency of the solution algorithm and linear relaxation-based heuristics.     

Joint planning of berth and yard allocation in transshipment terminals using multi-cluster stacking strategy

In this work, a joint planning problem for berth and yard allocation in transshipment terminals is addressed. Multi-cluster stacking strategy is proposed to split each transshipment flow into a number of container clusters and then stack each cluster in different yard blocks. A mixed integer quadratic programming model is formulated to minimize the total distance of exchanging containers between mother vessels and feeders, and the workload imbalance among yard blocks. A novel three-stage heuristic solution approach is developed and extensive numerical experiments are conducted to show the effectiveness of the proposed approach and the benefit of the multi-cluster strategy.     

A comparison of two exact methods for passenger railway rolling stock (re)scheduling

The assignment of rolling stock units to timetable services in passenger railways is an important optimization problem that has been addressed by many papers in different forms. Solution approaches have been proposed for different planning phases: strategic, tactical, operational, and real-time planning. In this paper we compare two approaches within the operational and real-time planning phase. The first exact approach is based on a known Mixed Integer Linear Program (MILP) which is solved using CPLEX. The second approach is a new method that is an extension of a recently introduced MILP, which is solved using a column and row generation approach. In this paper, we benchmark the performance of the methods on networks of two countries (Denmark and The Netherlands). We use the approaches to make daily schedules and we test their real time applicability by performing tests with different disruption scenarios. The computational experiments demonstrate that both models can be used on both networks and are able to find optimal rolling stock circulations in the different planning phases. Furthermore, the results show that both approaches are sufficiently fast to be used in a real-time setting.     

An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem

This problem involves optimizing product collection and redistribution from production locations to a set of processing plants over a planning horizon. This horizon consists of several days, and the collection-redistribution is performed on a repeating daily basis. A single routing plan must be prepared for the whole horizon, taking into account the seasonal variations in the supply. We model the problem using a sequence of periods, each corresponding to a season. We propose an adaptive large-neighborhood search with several specifically designed operators and features. The results show the excellent performance of the algorithm in terms of solution quality and computational efficiency.     

Planning and managing intermodal transportation of hazardous materials with capacity selection and congestion

The current literature in the rail–truck intermodal transportation of hazardous materials (hazmat) domain ignores congestion at intermodal yards. We attempt to close that gap by proposing a bi-objective optimization framework for managing hazmat freight that not only considers congestion at intermodal yards, but also determines the appropriate equipment capacity. The proposed framework, i.e., a non-linear MIP and a multi-objective genetic algorithm based solution methodology, is applied to a realistic size problem instance from existing literature. Our analysis indicates that terminal congestion risk is a significant portion of the network risk; and, that policies and tools involving number of cranes, shorter maximum waiting times, and tighter delivery times could have a positive bearing on risk.     

Optimisation of the exploitation period of individual vehicles in freight transportation companies

The individual vehicle replacement problem typical for freight transportation companies is discussed in the paper. Two characteristic features of such problem are that transportation companies utilise vehicles with intensity decreasing with an age of vehicles and that managers of such companies first of all take into account economical criteria when planning vehicle replacements. The paper presents a single criterion, nonlinear, deterministic and discrete mathematical model of such a problem that minimises a total exploitation and ownership costs calculated per kilometre. The exact solution procedure is proposed here. The problem is solved as a real life case study. As a result, an average, economically optimal 5-year exploitation period of vehicles has been determined.     

A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies

This paper discusses a dynamic evacuation network optimization problem that incorporates lane reversal and crossing elimination strategies. These two lane-based planning strategies complement one another by increasing capacity in specific directions through the evacuation network. A bi-level network optimization model is formulated, in which the upper level aims at optimizing the network evacuation performance subject to the lane-reversal and crossing-elimination constraints and the lower level conveys a cell transmission-based dynamic traffic assignment problem. An integrated Lagrangian relaxation and tabu search method is devised for approximating optimal problem solutions through an iterative optimization-evaluation process. The numerical results of implementing the developed modeling and solution approach to a synthetic network and a real-world example application justify its theoretical and practical value.     

Stochastic resource allocation for containerized cargo transportation networks when capacities are uncertain

We consider the stochastic resource allocation problem for containerized cargo transportation with uncertain capacities and network effects, in which a freight operator needs to allocate a certain amount of capacity to each product to maximize the expected profit. We formulate the problem as a constrained stochastic programming model and provide theoretical results that completely characterize the optimal solution to the model under a special case. Under a general case, we build an approximation model of the problem and propose a sampling based algorithm to solve the approximation model. A number of numerical experiments are offered to test the algorithm.     

Charting the coast: spatial planning for tourism using public participation GIS

Coastal tourism continues to experience sustained growth on a global scale, leading to concerns regarding socio-cultural, economic and environmental impacts. To-date, the explicit integration of tourism development with coastal management has lagged behind more traditional planning concerns, presenting an opportunity and challenge for managers. Spatial planning using public participation geographical information systems (PPGIS) offers one solution for integration that is cognisant of the centrality of place in tourism. PPGIS was used to document spatially explicit data on place values, activities and development preferences along the remote, Aboriginal-managed Port Smith (Purnturrpurnturr) coastline in Western Australia. The research was developed and implemented as a collaborative partnership between Aboriginal custodians and University researchers. Ninety-seven questionnaires containing participatory mapping were conducted with residents and visitors. The participatory mapping approach successfully identified areas of potential conflict and allows tourism planners and managers to implement spatial planning that explicitly recognises and accounts for visitor values and preferences. Tourism, as well as marine spatial planning, can be enhanced by a holistic approach that considers both tangible and intangible socio-spatial data. Such an approach is likely to foster a more nuanced appreciation of what is valued in the landscape, providing greater insights to support sustainable long-term planning.     

Bioethanol supply chain system planning under supply and demand uncertainties

A mixed integer stochastic programming model is established to support strategic planning of bioenergy supply chain systems and optimal feedstock resource allocation in an uncertain decision environment. The two-stage stochastic programming model, together with a Lagrange relaxation based decomposition solution algorithm, was implemented in a real-world case study in California to explore the potential of waste-based bioethanol production. The model results show that biowaste-based ethanol can be a viable part of sustainable energy solution for the future.