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.     

The congested multicommodity network design problem

This paper studies a version of the fixed-charge multicommodity network design problem where in addition to the traditional costs of flow and design, congestion at nodes is explicitly considered. The problem is initially modeled as a nonlinear integer programming formulation and two solution approaches are proposed: (i) a reformulation of the problem as a mixed integer second order cone program to optimally solve the problem for small to medium scale problem instances, and (ii) an evolutionary algorithm using elements of iterated local search and scatter search to provide upper bounds. Extensive computational results on new benchmark problem instances and on real case data are presented.     

Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth

This paper considers the berth allocation problem (BAP) with time-varying water depth at a tidal river port. Both integer programming (IP) and constraint programming (CP) models are developed. Numerical experiments find that CP tends to be superior to IP when the feasible domain is small (e.g. dynamic vessel arrivals), when the restriction of the objective towards decision variables is loose (e.g. makespan, departure delay), or when the size of IP models is too large due to fine time resolution. Meanwhile, CP’s incapability of proving optimality can be compensated by post-optimization with IP, by using a simple CP/IP hybrid procedure.     

An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem

This paper studies the heterogeneous fixed fleet vehicle routing problem (HFFVRP), in which the fleet is composed of a fixed number of vehicles with different capacities, fixed costs, and variable costs. Given the fleet composition, the HFFVRP is to determine a vehicle scheduling strategy with the objective of minimizing the total transportation cost. We propose a multistart adaptive memory programming (MAMP) and path relinking algorithm to solve this problem. Through the search memory, MAMP at each iteration constructs multiple provisional solutions, which are further improved by a modified tabu search. As an intensification strategy, path relinking is integrated to enhance the performance of MAMP. We conduct a series of experiments to evaluate and demonstrate the effectiveness of the proposed algorithm.     

A tabu search heuristic for the local container drayage problem under a new operation mode

This paper examines the Local Container Drayage Problem (LCDP) under an operation mode in which a tractor can be detached from its companion trailer and assigned to a new task. We have incorporated a set of temporal constraints into the classical VRP to realize this operation by utilizing the idle time available to tractors and coordinating the empty containers moving between customers. A tabu search algorithm is proposed. Some numerical experiments are conducted to assess the performance of the proposed algorithm, quantify the benefit of the new operation mode, and identify the conditions under which the mode is effective.     

A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges

This paper presents several heuristics for a variation of the vehicle routing problem in which the transportation fleet is composed of electric vehicles with limited autonomy in need for recharge during their duties. In addition to the routing plan, the amount of energy recharged and the technology used must also be determined. Constructive and local search heuristics are proposed, which are exploited within a non deterministic Simulated Annealing framework. Extensive computational results on varying instances are reported, evaluating the performance of the proposed algorithms and analyzing the distinctive elements of the problem (size, geographical configuration, recharge stations, autonomy, technologies, etc.).     

Variable neighborhood search heuristic for storage location assignment and storage/retrieval scheduling under shared storage in multi-shuttle automated storage/retrieval systems

This paper examines the joint optimization of storage location assignment and storage/retrieval scheduling in multi-shuttle automated storage/retrieval systems (AS/RSs) under shared storage, in which the reuse of empty location yielded by retrieval operation is allowed. From the view of analytical model, the advantage of operational mode under shared storage is verified. A variable neighborhood search (VNS) algorithm is developed to solve the large-sized problems. Various numerical experiments are conducted to evaluate the performance of the proposed algorithm and investigate the impact of different parameters on computational efficiency.     

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.     

Dynamic accessibility mapping using floating car data: a network-constrained density estimation approach

The concept of accessibility has been attracting increasing attention from transportation planners and researchers. The goal of “smart growth” is to promote accessibility rather than mobility. Accessibility mapping is a highly effective tool to support smart growth planning. Studies on accessibility mapping and analysis have proliferated over the last decade as Geographic Information Systems (GIS) has been widely adopted to produce accessibility maps. Nevertheless, a major negative aspect of these efforts is the lack of dynamic access measurement. Traffic conditions change significantly over space and time, leading to non-stationary travel time estimation which is central to accessibility measurement. In this paper, we propose a dynamic accessibility measure based on real-time travel speeds that are derived from floating car data (FCD). We introduce a novel integrated access measure to compute accessibility to Points of Interest (POIs) constrained by road networks. POI accessibility measures are obtained by means of both Network Kernel Density Estimation (NKDE) and Network Linear Density Estimation (NLDE). Therefore, we are able to capture temporal dynamics by taking into account speed variability using FCD during peak and off-peak hours on weekdays and weekends. We demonstrate that the proposed approach can capture the spatio-temporal dynamics of accessibility using FCD for Wuhan city in China. Empirical studies were conducted to examine the impacts of density estimation parameters (search bandwidths) and POI weights on the integrated accessibility. We find that search bandwidth and POI weights would impose profound influence on final accessibility values. Experiments also show that NKDE and NLDE would produce significantly different estimation results.     

Stochastic optimization models for the airport gate assignment problem

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.     

A novel heuristic approach for solving aircraft landing problem with single runway

Nowadays, airlines administrations are more willing to utilize optimization tools to control air traffic due to considerable increases in volume of air transports. A challenging problem in the field of air traffic is how to optimally schedule landing time of aircrafts and assign them to different runways such that early and late landing costs are minimized. This problem is called aircraft landing problem (ALP). This paper proposes a novel decomposition based heuristic by solving two sub-problems for the ALP with single runway. In the first sub-problem, we apply the adaptive large neighborhood search (ALNS) algorithm to find a sequence of aircrafts. The solution found in the first sub-problem will be sent to the second sub-problem, to check for the feasibility of the solution using CPLEX solver. A set of benchmark problem are taken from the OR library for the purpose of comparison with other existing approaches. The computational results exhibit that the proposed algorithm is capable of finding the best known optimal solution for all the instances.     

The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion

The green vehicle routing and scheduling problem (GVRSP) aims to minimize green-house gas emissions in logistics systems through better planning of deliveries/pickups made by a fleet of vehicles. We define a new mixed integer liner programming (MIP) model which considers heterogeneous vehicles, time-varying traffic congestion, customer/vehicle time window constraints, the impact of vehicle loads on emissions, and vehicle capacity/range constraints in the GVRSP. The proposed model allows vehicles to stop on arcs, which is shown to reduce emissions up to additional 8% on simulated data. A hybrid algorithm of MIP and iterated neighborhood search is proposed to solve the problem.     

单车场大规模车辆路径优化问题研究

针对传统优化技术在解决大规模车辆路径问题中存在的缺陷,提出了一种解决单车场大规模车辆路径优化问题的综合启发式算法。首先,采用Sweep技术将区域分解成几个子区。其次,设计了分区的禁忌搜索算法,并采用相邻区域综合优化技术,提高了算法的全局搜索能力。仿真试验表明,该算法能够有效解决大规模车辆路径优化问题。     

Optimizing road network daily maintenance operations with stochastic service and travel times

This paper studies optimization methods for a routing problem encountered in daily maintenance operations of a road network. Stochastic service and travel times on road segments are considered. The problem is formulated as a variation of the capacitated arc routing problem (CARP). A chance-constrained programming model is firstly developed and solved by a branch-and-cut algorithm. A stochastic programming model with recourse is also proposed to take into account the recourse costs in case of route failure. The problem is solved by an adaptive large neighborhood search algorithm. The computational experiments demonstrate the effectiveness of the algorithm.     

基于收益管理理论的铁路客运专线价格策略研究简

在我国高速铁路网快速发展的背景下,有必要对铁路客运网络与旅客出行行为的关系进行深入研究,为路网规划提供参考依据。基于路网规划阶段确定的包含高速铁路与普速铁路的网络布局结构特征,对铁路旅客出行路径的选择倾向进行研究,建立了用于反映铁路旅客出行路径选择倾向的多项Logit模型,提出了相应的铁路旅客出行路径搜索算法,通过算例分析,验证了模型与算法的有效性,并对铁路路网规划工作提出建议。     

The airfare pricing and seat allocation problem in full-service carriers and subsidiary low-cost carriers

This study investigates the competitive market situation in the air transport industry considering full-service carriers (FSC), subsidiary low-cost carriers (LCC) and rival LCCs on the flight-leg level while subsidiary LCCs are established by FSCs against rival LCCs to keep the market share and to make more profit. It is assumed that the demand of economy class for each airline follows a known distribution, and the mean value of that distribution is a function of its airfare and the airfare differences with other airlines. In addition, no-shows and cancellations are introduced to reflect a real situation. Based on this situation, a mathematical model is developed to derive efficient airfare pricing and seat allocation for each airline for maximizing the profit sum of both FSCs and subsidiary LCCs using a repeated game. A repeated game model integrated with a Tabu search algorithm and an EMSR based heuristic is suggested to deal with the proposed repeated game. A numerical example is provided to validate the model and solution procedure with hypothetical system parameter values under two kinds of market situations that show before and after the emergence of subsidiary LCCs.     

Ex-post identification of geographical extent of benefited area by a transportation project: Functional data analysis method

This study proposes an approach for ex-post identification of the geographical extent of an area benefiting from a transportation project, using functional data analysis methods. Our approach focuses on real estate (land) price data for the ex-post spatial evaluation. First, we prepare a panel of land prices observed before, during, and after the project in the areas that are potentially impacted. Second, using functional data analysis, movements of land prices in each observed site during the target period are approximated by continuous functions. Third, using the functional ordinary Kriging technique, the functions for land price movements in each micro district are spatially predicted. Lastly, by employing the functional clustering (functional K-means) technique, potential areas of benefit may be identified. Different from exiting before-and-after methods, including difference-in-differences method, the proposed procedure based on functional data analysis can describe a map with a complex spatial distribution pattern of benefit rather than using distance bands (ring buffer) from transportation cores, such as railway stations, bus stops, and highway interchanges. Then, the proposed procedure is empirically applied to a large-scale Japanese heavy railway project. The obtained result shows so-called redistributive effect, that is, land prices decrease around exiting stations and increase around new stations. In addition, interestingly enough, the spatial distribution pattern of the identified areas of benefit using this procedure are fairly similar to that of ex-ante predicted areas of benefit by the hedonic approach. Thus, capitalization is observationally confirmed with regard to accessibility improvement.     

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.     

Scheduling trucks in cross-docking systems: A robust meta-heuristics approach

In a cross-docking system, trucks must be scheduled to minimize the total flow time of the system. This problem is NP-hard, and this study proposes two hybrid meta-heuristics—hybrid simulated annealing and hybrid variable neighborhood search—to solve it by achieving the best sequence of truck pairs. The Taguchi method serves to reveal the best robustness of these algorithms. To demonstrate the effectiveness of the proposed methods, especially for large-sized problems, this study solves various test problems, and the computational results clearly reveal that the proposed methods outperform previous approaches.