Min–Max exact and heuristic policies for a two-echelon supply chain with inventory and transportation procurement decisions

We study the problem in which one supplier delivers a product to a set of retailers over time by using an outsourced fleet of vehicles. Since the probability distribution of the demand is not known, we provide a Min–Max approach to find robust policies. We show that the optimal Min-Expected Value policy can be very poor in the worst case. We provide a Min–Max Dynamic Programming formulation that allows us to exactly solve the problem in small instances. Finally, we implement a Min–Max Matheuristic to solve benchmark instances and show that it is very effective.     

Optimising flight connection times in airline bank structure through Simulated Annealing and Tabu Search algorithms

In hub and spoke airline networks, flight arrivals and departures generally have a bank structure to increase connections among spoke cities through a hub airport in order to provide cheaper service for higher volumes of air traffic. In this study, we introduce the airline bank optimisation problem with a novel mathematical model for improving flight connection times. The mathematical model aims to minimise the total connection times for transfer passengers and generates flight schedules regarding slot capacities in the hub airports. Since the problem is a combinatorial optimisation problem NP-hard and computational complexity increases rapidly for real-world problems, we employ the simulated annealing and the tabu search algorithms to achieve better solutions in a reasonable time. We generate sub-problems using real-world data and investigate the effectiveness of the algorithms. Finally, we present the results of a real case study of a Turkish airline company which has a hub airport connecting the flights between Middle Eastern and European cities.     

A dynamic approach for aircraft assignment and maintenance scheduling by airlines

The problems of assigning planes to flights and of fleet maintenance operations scheduling are considered in this paper. While recent approaches make use of artificial intelligence techniques running on main frame computers to solve combinatorial optimization problems for nominal operations, a dynamic approach is proposed here to face on-line operation conditions. The proposed solution mixes a Dynamic Programming approach (to cope with the fleet assignment problem) and a heuristic technique (to solve the embedded maintenance schedule problem). When applied to a medium charter airline, this approach shows acceptability characteristics for operational staffs, while providing efficient solutions. The proposed solution scheme can be considered as the basis for the development of an on-line decision support system for fleet operations management within airlines.     

An optimal approach for a set covering version of the refueling-station location problem and its application to a diffusion model

This article deals with the refueling-station location problem for alternative fuel vehicles in a traffic network. Alternative fuel vehicles can be characterized by the vehicle range that limits the travelable distance with fuel at full capacity. I propose an efficient formulation of the refueling-station location problem using an optimal property and prove that the problem is NP(Non-deterministic Polynomial)-complete in the strong sense. I consider a special case of the refueling-station location problem in which the construction costs are equal for all nodes. In this case, the problem is to determine refueling station locations to minimize the total number of stations, while making the possible multiple predetermined origin–destination round-trips. I propose an optimal algorithm applicable when no refueling stations currently exist in a traffic network and a dynamic programming based algorithm applicable when a set of refueling stations already exists. I apply the algorithms to a traffic network to study the diffusion of refueling stations and predict the speed and range of station establishment. The computational experiments show that the speed of diffusion depends on the vehicle range and the sequence of the origin–destination demands considered in the diffusion process.     

Comparing heuristic algorithms of the planar storage location assignment problem

This paper discusses the newly defined planar storage location assignment problem (PSLAP). We develop a mathematical programming model and GA-based and dynamic PSLAP heuristic algorithms for the solving procedure. Using the testing set, we compare the performance of GA-based and dynamic PSLAP heuristic algorithms. The mathematical programming model is utilized as a comparison criterion. The comparison results demonstrate that the dynamic PSLAP heuristic algorithm performs better than the other solving procedures. In addition, we describe simulation experiments conducted to investigate the effects of stock yard layout and production schedule instability on the operation of the block stock yard.     

The Electric Traveling Salesman Problem with Time Windows

To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.     

Handling uncertainties in vehicle routing problems through data preprocessing

This paper presents a global preprocessing methodology for handling uncertainties in operations management. Beyond theoretical considerations on solution feasibility, the methodology provides practitioners with a Monte Carlo simulation-based framework for effective risk management. The main strength of this methodology is being easily applicable to almost any decision problem. Application field of the paper is a real-life workforce management problem for which we propose several mixed integer formulations as well as dedicated solution algorithms. Extensive numerical tests on real-life instances assess the benefit from preprocessing schemes when performed as recommended by our approach, and thus prove its practical relevance.     

A Linear Programming approach for robust network revenue management in the airline industry

The classical revenue management problem consists of allocating a fixed network capacity to different customer classes, so as to maximize revenue. This area has been widely applied in service industries that are characterized by a fixed perishable capacity, such as airlines, cruises, hotels, etc.It is traditionally assumed that demand is uncertain, but can be characterized as a stochastic process (See Talluri and van Ryzin (2005) for a review of the revenue management models). In practice, however, airlines have limited demand information and are unable to fully characterize demand stochastic processes. Robust optimization methods have been proposed to overcome this modeling challenge. Under robust optimization framework, demand is only assumed to lie within a polyhedral uncertainty set (Lan et al. (2008); Perakis and Roels (2010)).In this paper, we consider the multi-fare, network revenue management problem for the case demand information is limited (i.e. the only information available is lower/upper bounds on demand). Under this interval uncertainty, we characterize the robust optimal booking limit policy by use of minimax regret criterion. We present an LP (Linear Programming) solvable mathematical program for the maximum regret so our model is able to solve large-scale problems for practical use. A genetic algorithm is proposed to find the booking limit control to minimize the maximum regret. We provide computational experiments and compare our methods to existing ones. The results demonstrate the effectiveness of our robust approach.     

A robust inventory routing policy under inventory inaccuracy and replenishment lead-time

In this paper, we study an inventory routing problem under replenishment lead-time and inventory inaccuracy, which exist extensively in distribution systems for fresh products, but are often ignored in existing research. To solve the problem, a robust inventory routing policy is developed in three steps. At first, we propose the methods of updating the probability of the current net inventory and predicting those in future periods. For each candidate route, we develop a Robust TQL Algorithm to optimize the replenishment time, replenishment quantity and replenishment stage length. Finally, a genetic algorithm-based method is developed to optimize the delivery route.     

Anticipatory algorithms for same-day courier dispatching

This paper describes anticipatory algorithms for the dynamic vehicle dispatching problem with pickups and deliveries, a problem faced by local area courier companies. These algorithms evaluate alternative solutions through a short-term demand sampling and a fully sequential procedure for indifference zone selection. They also exploit an unified and integrated approach in order to address all the issues involved in real-time fleet management, namely assigning requests to vehicles, routing the vehicles, scheduling the routes and relocating idle vehicles. Computational results show that the anticipatory algorithms provide consistently better solutions than their reactive counterparts.     

An outer approximation algorithm for the robust shortest path problem

This paper describes a new algorithm for the stochastic shortest path problem where path costs are a weighted sum of expected cost and cost standard deviation. We allow correlation between link costs, subject to a regularity condition excluding unbounded solutions. The chief complication in this variant is that path costs are not an additive sum of link costs. In this paper, we reformulate this problem as a conic quadratic program, and develop an outer-approximation algorithm based on this formulation. Numerical experiments show that the outer-approximation algorithm significantly outperforms standard integer programming algorithms implemented in solvers.     

Deployment and utilization of plug-in electric vehicles in round-trip carsharing systems

Electric Vehicles (EVs) and Plug-in Hybrid Electric Vehicles (PHEVs) can reduce gasoline consumption, but increase vehicle acquisition costs and introduce operational constraints. We develop a comprehensive approach to EV/PHEV deployment and utilization in round-trip carsharing systems. First, we formulate and solve the tactical problem of utilizing a mix of gasoline vehicles and EVs/PHEVs to serve trip demand, using Mixed Integer Programming optimization to estimate the minimal gasoline consumption in a computationally efficient manner, and simulation to assess the effect of reservation order on realized gasoline consumption. Second, we use these results to inform the strategic deployment of EVs/PHEVs in the carsharing fleet, using meta-optimization. We implement our approach using data from a large carsharing provider. From the perspective of a carsharing operator, our results suggest that replacing some portion of existing gasoline fleets by EVs/PHEVs would result in gasoline savings likely to outweigh upfront investments and the constraints on vehicle utilization that it creates. Moreover, we find that easily implementable heuristics can capture some of these benefits, and that the integration of vehicle utilization patterns into the design of EV/PHEV deployment strategies can result in added benefits.     

Optimal placement of multiple types of detectors under a small vessel attack threat to port security

We focus on a threat scenario where a terrorist would utilize a small vessel to attack a maritime target. We consider how to place multiple types of detectors to protect maritime targets from such an attack. Detectors are not perfectly reliable. The resulting detector placement problem is formulated as a nonlinear binary integer program such that the expected damage cost caused by the small vessel attack is minimized. Two exact algorithms and a greedy adding heuristic are proposed. Moreover, we conduct a detailed computational study and provide a case study in New York Harbor.     

Reformulating Environmentally Constrained Traffic Equilibrium via a Smooth Gap Function

Various government laws have recently been enacted to alleviate the environmental deterioration of transportation systems. Environmental constraint is a valid means to explicitly reflect various environmental protection requirements imposed by the government. In this paper, we examine the environmentally constrained traffic equilibrium problem (EC-TEP), which is a fundamental tool for modeling and evaluating environmental protection requirements. Specifically, we provide an equivalent reformulation for the EC-TEP. The proposed reformulation adapts the concept of gap function to simultaneously reformulate the nonlinear complementarity conditions associated with the generalized user equilibrium conditions, environmental constraints, and conservation constraints as an equivalent unconstrained optimization problem. This gap function reformulation has two desirable features: (1) it can handle a general environmental constraint structure (linear or nonlinear; link-based or area-based) and a general link and route cost structure, enhancing the modeling adaptability and flexibility; (2) it is smooth and unconstrained, permitting a number of existing efficient algorithms for its solution. A gradient-based solution algorithm with a self-regulated averaging stepsize scheme is customized to solve the reformulated unconstrained optimization problem. Numerical examples are also provided to demonstrate the modeling flexibility of the proposed EC-TEP reformulation.     

Criteria selection and multi-objective optimization of aircraft landing problem

Inspired by the similarities of the aircraft landing problem (ALP) and the single machine scheduling problem, we propose a criteria selection method that has been used successfully in the single machine scheduling problem to determine appropriate objective functions of ALP. First, for four different types of criteria—min-max, min-sum, completion time related, and due-dates related criteria—their corresponding physical meanings in ALP are elaborated. Then, a criteria selection method is proposed to determine several appropriate criteria, which are taken as the multi-objective while modeling ALP. Different solution algorithms, including Imperialist Competitive Algorithm (ICA), are adopted to solve the multi-objective ALP. Finally, the performance of the proposed model and method are evaluated using a set of benchmark instances. The computational results demonstrate the efficiency of our approach for solving ALP, which can simultaneously improve punctual performance, enhance runway utilization, reduce air traffic controller workload, and maintain equity among airlines.     

Routing and refueling plans to minimize travel time in alternative-fuel vehicles

A driver who drives an alternative-fuel vehicle (AFV) from an origin point to a destination point needs to consider how to get there (i.e., the routing problem), when to stop, and how and when to refuel (i.e., the refueling plan). In this study, models and algorithms are proposed that optimize a one-way-trip path such that the total travel time from the origin to the destination is minimized. The travel time consists of the setup time, the refueling time and the driving time. The setup time includes waiting for the AFV to be served at a refueling station and the preparation time of charging the machine. We categorized the problems into two types: (1) the refueling plan problem when the routing decision is given and (2) an integrated problem of routing and refueling. Another axis of categorization is when (1) setup time and refueling times are site-independent and (2) parameters are site-dependent. We propose optimal algorithms for site-independent problems and the integrated problem of routing and refueling planning with site-independent parameters. We also conduct experiments and sensitivity analyses for the site-dependent integrated problems of routing and refueling.     

Optimal distance tolls under congestion pricing and continuously distributed value of time

This paper addresses the optimal distance-based toll design problem for cordon-based congestion pricing schemes. The optimal distance tolls are determined by a positive and non-decreasing toll-charge function with respect to the travel distance. Each feasible toll-charge function is evaluated by a probit-based SUE (Stochastic User Equilibrium) problem with elastic demand, asymmetric link travel time functions, and continuously distributed VOT, solved by a convergent Cost Averaging (CA) method. The toll design problem is formulated as a mixed-integer mathematical programming with equilibrium constraints (MPEC) model, which is solved by a Hybrid GA (Genetic Algorithm)–CA method. Finally, the proposed models and algorithms are assessed by two numerical examples.     

Container drayage problem with flexible orders and its near real-time solution strategies

This article studies a container drayage problem with flexible orders defined by using requiring and releasing attributes as a unified formulation of various order types. A determined-activities-on-vertex (DAOV) graph introduces a temporary vertex set to formulate different truck statuses. The problem is formulated as a mixed-integer nonlinear programming model based on the DAOV graph. Four strategies including a window partition based (WPB) strategy are presented and evaluated extensively to solve the problem. Results indicate that the WPB method could solve the problem effectively and efficiently. Furthermore, this method is robust considering the operating time biases compared to other algorithms.     

基于遗传模拟退火算法的战时物流配送路径优化研究

综合考虑战时物流配送车辆路径问题（VRP）的多目标评价，提出多属性道路网络下战时物流配送的VRP算法，并建立完全分层优化模型。将进化算法与传统优化技术相结合，构造了模型的两层求解算法，第一层采用遗传算法和模拟退火算法混合的GASA算法，第二层采用枚举法。并以成品燃油配送为例进行了实验，结果表明算法较标准遗传算法更有效。     

Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem

The Heterogeneous Dial-a-Ride Problem (HDARP) is an important problem in reduced mobility transportation. Recently, several extensions have been proposed towards more realistic applications of the problem. In this paper, a new variant called the Multi-Depot Multi-Trip Heterogeneous Dial-a-Ride Problem (MD-MT-HDARP) is considered. A mathematical programming formulation and three metaheuristics are proposed: an improved Adaptive Large Neighborhood Search (ALNS), Hybrid Bees Algorithm with Simulated Annealing (BA-SA), and Hybrid Bees Algorithm with Deterministic Annealing (BA-DA). Extensive experiments show the effectiveness of the proposed algorithms for solving the underlying problem. In addition, they are competitive to the current state-of-the-art algorithm on the MD-HDARP.