The competitive facility location problem under disruption risks

Two players sequentially locate a fixed number of facilities, competing to capture market share. Facilities face disruption risks, and each customer patronizes the nearest operational facility, regardless of who operates it. The problem therefore combines competitive location and location with disruptions. This combination has been absent from the literature. We model the problem as a Stackelberg game in which the leader locates facilities first, followed by the follower, and formulate the leader’s decision problem as a bilevel optimization problem. A variable neighborhood decomposition search heuristic which includes variable fixing and cut generation is developed. Computational results suggest that high quality solutions can be found quickly. Interesting managerial insights are drawn.     

Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads

This paper addresses the routing problem with unpaired pickup and delivery with split loads. An interesting factor of our problem is that the quantity and place for pickup and delivery are decision variables in the network. We develop an easy-to-implement heuristic in order to gain an efficient and feasible solution quickly. Then, a local search algorithm based on the variable neighborhood search (VNS) method is developed to improve the performance of the heuristic. Computational results show that the proposed VNS method is able to obtain an optimal or near optimal solution in reasonable time for the formulated problem.     

Joint location-inventory problem with differentiated service levels using critical level policy

This paper analyzes the design of a distribution network for fast-moving items able to provide differentiated service levels in terms of product availability for two demand classes (high and low priority) using a critical level policy. The model is formulated as a MINLP with chance constraints for which we propose a heuristic to solve it. Although the heuristic does not guarantee an optimal solution, our computational experiments have shown that it provides good-quality solutions that are on average 0.8% and at worst 2.7% from the optimal solution.     

Scheduling technicians for planned maintenance of geographically distributed equipment

A real-world planned maintenance scheduling problem that exists at several business units within United Technologies Corporation (UTC) is addressed in this paper. The scheduling problem is formulated as a multiple tour maximum collection problem with time-dependent rewards and an adaptive memory tabu search heuristic is developed to solve it. The effectiveness of the proposed solution approach is examined using real-world problem instances supplied by UTC. Relevant upper bounds are derived for the application. Results of numerical experiments indicate that the proposed tabu search heuristic is able to obtain near optimal solutions for large-size (i.e., actual) problem instances in reasonable computation time.     

A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling,with consideration of fleet assignment problem

One of the most important airline's products is to determine the aircraft routing and scheduling and fleet assignment. The key input data of this problem is the traffic forecasting and allocation that forecasts traffic on each flight leg. The complexity of this problem is to define the connecting flights when passengers should change the aircraft to reach the final destination. Moreover, as there exists various types of uncertainties during the flights, finding a solution which is able to absorb these uncertainties is invaluable. In this paper, a new robust mixed integer mathematical model for the integrated aircraft routing and scheduling, with consideration of fleet assignment problem is proposed. Then to find good solutions for large-scale problems in a rational amount of time, a heuristic algorithm based on the Simulated Annealing (SA) is introduced. In addition, some examples are randomly generated and the proposed heuristic algorithm is validated by comparing the results with the optimum solutions. The effects of robust vs non-robust solutions are examined, and finally, a hybrid algorithm is generated which results in more effective solution in comparison with SA, and Particle Swarm Optimization (PSO).     

The capacitated plant location problem with customers and suppliers matching

This paper introduces a new problem called the capacitated plant location problem with customer and supplier matching (CLCSM). The product distribution from plants to customers and the material supply from suppliers to plants are considered together. We merge a distribution trip and a supply trip into one triangular trip for saving allocation cost. Vehicles from plants visit a customer and a supplier for each trip. We provide a heuristic solution procedure based on Lagrangian relaxation. Computational results indicate that the proposed heuristic solution procedure is shown to be efficient yielding optimal or near-optimal solutions for randomly generated instances.     

Berth scheduling by customer service differentiation: A multi-objective approach

In this paper the discrete and dynamic berth allocation problem is formulated as a multi-objective combinatorial optimization problem where vessel service is differentiated upon based on priority agreements. A genetic algorithms based heuristic is developed to solve the resulting problem. A number of numerical experiments showed that the heuristic performed well in solving large, real life instances. The heuristic provided a complete set of solutions that enable terminal operators to evaluate various berth scheduling policies and select the schedule that improves operations and customer satisfaction. The proposed algorithm outperformed a state of the art metaheuristic and provided improved results when compared to the weighted approach.     

Solving a static repositioning problem in bike-sharing systems using iterated tabu search

In this paper, we study the static bike repositioning problem where the problem consists of selecting a subset of stations to visit, sequencing them, and determining the pick-up/drop-off quantities (associated with each of the visited stations) under the various operational constraints. The objective is to minimize the total penalties incurred at all the stations. We present an iterated tabu search heuristic to solve the described problem. Experimental results show that this simple heuristic can generate high quality solutions using small computing times.     

Designing robust routes for demand-responsive transport systems

In this study, we propose an innovative concept for robust demand-responsive transportation (DRT) systems where vehicles may deviate from the planned route to accept late requests, which are unknown during the planning stage. We propose a new formulation of the problem as a stochastic mixed integer program and describe an efficient heuristic procedure that embeds a tabu search approach in a scheme for merging different scenario solutions. The computational results demonstrate the validity of the heuristic and provide useful managerial insights into DRT systems, thereby showing the value of incorporating uncertainty into the planning process.     

Exact and heuristic methods to solve the berth allocation problem in bulk ports

In this paper, we study the dynamic hybrid berth allocation problem in bulk ports with the objective to minimize the total service times of the vessels. We propose two exact methods based on mixed integer programming and generalized set partitioning, and a heuristic method based on squeaky wheel optimization, explicitly considering the cargo type on the vessel. The formulations are compared through extensive numerical experiments based on instances inspired from real bulk port data. The results indicate that the set partitioning method and the heuristic method can be used to obtain near-optimal solutions for even larger problem size.     

Combining Lagrangian heuristic and Ant Colony System to solve the Single Source Capacitated Facility Location Problem

The facility location problems have been applied extensively in practice. We describe a Multiple Ant Colony System (MACS) to solve the Single Source Capacitated Facility Location Problem (SSCFLP). Lagrangian heuristics have been shown to produce good solutions for the SSCFLP. A hybrid algorithm, which combines Lagrangian heuristic and Ant Colony System (ACS), LH–ACS, is developed for the SSCFLP. The performance of the proposed methods are tested on two sets of benchmark instances and compared with other heuristic algorithms in the literature. The computational results indicate that both MACS and LH–ACS are effective and efficient for the SSCFLP and competitive with other well-known algorithms.     

A heuristic approach to logistics network design for end-of-lease computer products recovery

This paper discusses the logistics network design for end-of-lease computer products recovery by developing a deterministic programming model for systematically managing forward and reverse logistics flows. Due to the complexity of such network design problem, a two-stage heuristic approach is developed to decompose the integrated design of the distribution networks into a location–allocation problem and a revised network flow problem. The applicability of the proposed method is illustrated in a numerical study. Computational experiments demonstrate that high-quality solutions are obtained while modest computational overheads are incurred.     

The multi-period service territory design problem – An introduction,a model and a heuristic approach

In service territory design applications, a field service workforce is responsible for providing recurring services at their customers’ sites. We introduce the associated planning problem, which consists of two subproblems: In the partitioning subproblem, customers must be grouped into service territories. In the scheduling subproblem, customer visits must be scheduled throughout the multi-period planning horizon. The emphasis of this paper is put on the scheduling subproblem. We propose a mixed integer programming model for this subproblem and present a location-allocation heuristic. The results of extensive experiments on real-world instances show that the proposed heuristic produces high-quality solutions.     

Towards a decision-support tool for airport slot allocation: Application to Guarulhos (Sao Paulo,Brazil)

In the vast majority of airports where demand exceeds capacity, landing and take-off slots are allocated according to the process established by the Worldwide Slot Guidelines (WSG). An optimization-based decision-support tool is introduced in this paper to assist slot coordinators in the initial slot allocation – the most important stage of that process. The WSG comprises both primary and additional criteria to be taken into account by slot coordinators at this stage. Considering all additional criteria specified in the WSG, this tool generates, in an acceptable amount of time, alternative efficient slot allocations against which the coordinators can evaluate the solutions obtained through the heuristic methods they apply. The decision-support tool also offers solution analysis features, such as visualization, ranking, comparison of multiple optimal solutions, and comparison of solutions regarding important characteristics not reflected in the WSG additional criteria. The tool is being tested at one of the largest airports worldwide – Guarulhos (Sao Paulo, Brazil) – with results that clearly illustrate its usefulness in practice.     

A robust optimization approach to the integrated berth allocation and quay crane assignment problem

This paper investigates the integrated berth allocation and quay crane assignment problem in container terminals. A deterministic model is formulated by considering the setup time of quay cranes. However, data uncertainties widely exist, and it may cause the deterministic solution to be infeasible. To handle the uncertainties, a robust optimization model is established. Furthermore, to control the level of conservativeness, another robust optimization model with the price constraints is proposed. A genetic algorithm and an insertion heuristic algorithm are suggested to obtain near optimal solutions. Computational experiments indicate that the presented models and algorithms are effective to solve the problems.     

A heuristic algorithm for yard truck scheduling and storage allocation problems

The yard truck scheduling and the storage allocation are two important decision problems affecting the efficiency of container terminal operations. This paper proposes a novel approach that integrates these two problems into a whole. The objective is to minimize the weighted sum of total delay of requests and the total travel time of yard trucks. Due to the intractability of the proposed problem, a hybrid insertion algorithm is designed for effective problem solutions. Computational experiments are conducted to examine the key factors of the problem and the performance of the proposed heuristic algorithm.     

Robust global supply chain network design under disruption and uncertainty considering resilience strategies: A parallel memetic algorithm for a real-life case study

A mixed-integer, non-linear model is developed for designing robust global supply chain networks under uncertainty. Six resilience strategies are proposed to mitigate the risk of correlated disruptions. In addition, an efficient parallel Taguchi-based memetic algorithm is developed that incorporates a customized hybrid parallel adaptive large neighborhood search. Fitness landscape analysis is used to determine an effective selection of neighborhood structures, while the upper bound found by Lagrangian relaxation heuristic is used to evaluate quality of solutions and effectiveness of the proposed metaheuristic. The model is solved for a real-life case of a global medical device manufacturer to extract managerial insights.     

A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts

We propose a new multi-start solution approach for the split-delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA). Initial solutions are generated by both node-insertion and route-addition procedures with a single parameter to control the restart. These solutions are then improved by a variable neighborhood descent metaheuristic with a novel search operator inspired by node-ejection chains. We test the proposed approach with 32 benchmark instances for four different minimum delivery fractions. Using the proposed algorithm, out of 128 cases tested, we find 81 best known solutions and 34 new best solutions; overall, we find 43 new best solutions.     

Stochastic fleet deployment models for public bicycle rental systems

This paper presents two stochastic bike deployment (SBD) models that determine the optimal number of bicycles allocated to each station in a leisure-oriented public bicycle rental system with stochastic demands. The SBD models represent the stochastic demands using a set of scenarios with given probabilities. A multilayer bike-flow time-space network is constructed for developing the models, where each layer corresponds to a given demand scenario and effectively describes bicycle flows in the spatial and temporal dimensions. As a result, the models are formulated as the integer multi-commodity network flow problem, which is characterized as NP-hard. We propose a heuristic to efficiently obtain good quality solutions for large-size model instances. Test instances are generated using real data from a bicycle rental system in Taiwan to evaluate the performance of the models and the solution algorithm. The test results show that the models can help the system operator of a public bicycle system make effective fleet deployment decisions.     

The generalized lock scheduling problem: An exact approach

The present paper introduces an integrated approach to solving the generalized lock scheduling problem. Three interrelated sub problems can be discerned: ship placement, chamber assignment and lockage operation scheduling. In their turn, these are closely related to the 2D bin packing problem, the assignment problem and the (parallel) machine scheduling problem respectively. In previous research, the three sub problems mentioned were considered separately, often using (heuristic) interaction between them to obtain better solutions. A mixed integer linear programming model is presented and applied to instances from both inland locks and locks in a tide independent port. The experiments show that small instances incorporating a wide range of real-life constraints can be solved to optimality.