A robust optimization approach for the road network daily maintenance routing problem with uncertain service time

This paper studies the robust optimization approach for the routing problem encountered in daily maintenance operations of a road network. The uncertainty of service time is considered. The robust optimization approach yields routes that minimize total cost while being less sensitive to substantial deviations of service times. A robust optimization model is developed and solved by the branch-and-cut method. In computational experiments, the behavior of the robust solutions and their performance are analyzed using Monte Carlo simulation. The robust optimization model is also compared with a classic chance-constrained programming model. The experimental analysis provides managerial insights for decision makers to determine an appropriate routing strategy.     

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.     

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.     

A hybrid population heuristic for the heterogeneous vehicle routing problems

The heterogeneous vehicle routing problem (HVRP) plays an important role in supply chain logistics. Two variants of HVRP are treated in this paper: one with fixed and variable costs (HVRPFD), and the other with only variable cost (HVRPD). A hybrid population heuristic that is able to solve both variants is proposed, in which a population of solutions are progressively evolved by crossovers and local searches. Computational results on a set of eight benchmark test problems from literature show that the proposed heuristic produces excellent solutions in short computing times.     

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.     

A large neighborhood search heuristic to establish an optimal ad-hoc hubbing strategy in the wake of a large-scale airport outage

Abrupt airport outages can cause diversions and fuel-critical situations for flights, leading to costly passenger misconnections. We develop a large neighborhood search heuristic to optimize the rerouting of flights bound for a disrupted airport to a hub airport that is not disrupted, with the goal of accommodating passengers on existing flights departing the non-disrupted hub. The objective of the heuristic is to identify and reroute flights to the ad-hoc hub(s) – non-disrupted hub airport(s) – that minimize the sum of passenger travel time and wait time. We minimize the passenger cost as the sum of passenger travel time to the diversion airport and wait time for a connecting flight at the ad-hoc hub airport, subject to on-board fuel and diversion airport capacity constraints. We use the heuristic to determine how a coordinated traffic management strategy could have diverted flights immediately following a real-world airport outage.     

An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport

Door-to-Door service of Pickup and Delivery of Customers to the Airport (D2PDCA) is a new service provided by certain Airline Ticket Sales Agencies (ATSAs) in China. This new service provides an attractive alternative way by picking up customer at this/her specified position and at any time he/she preferred and delivering to the airport more conveniently than airport shuttle and thus earn high customer service quality. Compared with the single-trip mode, the multi-trip mode of D2PDCA (MTM-D2PDCA) service can reduce travel distances, the number of vehicles required and the operating cost. To obtain the exact solution of the MTM-D2PDCA problem, we propose a novel, exact algorithm based on the trip-chain-oriented set-partitioning (TCO-SP) model, where a trip-chain represents multiple trips made by a specific vehicle. In the exact algorithm, we propose an improved label-correcting method to remove infeasible trip-chains quickly and thus speed the search process. Based on the feasible trip-chains, the MTM-D2PDCA problem is formulated as the novel TCO-SP model, which can be solved exactly by the optimization software CPLEX. In addition, we present several mathematical insights into the relationship between the number of trip-chains and the number of local optimal trips that are applicable in both theory and practice. Extensive experiments are conducted to illustrate the application of the model and demonstrate the cost savings of the MTM-D2PDCA mode over the single-trip mode and provide managerial insights into successfully operating a MTM-D2PDCA service.