The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics

An algorithm that can tackle time dependent vehicle routing problems with hard or soft time windows without any alteration in its structure is presented. Analytical and experimental results indicate that average computational time increases proportionally to the number of customers squared. New replicable test problems that capture the typical speed variations of congested urban settings are proposed. Solution quality, time window perturbations, and computational time results are discussed as well as a method to study the impact of perturbations by problem type. The algorithm efficiency and simplicity is well suited for urban areas where fast running times may be required.     

Analysis of an integrated maximum covering and patrol routing problem

In this paper, we address the problem of determining the patrol routes of state troopers for maximum coverage of highway spots with high frequencies of crashes (hot spots). We develop a specific mixed integer linear programming model for this problem under time feasibility and budget limitation. We solve this model using local and tabu-search based heuristics. Via extensive computational experiments using randomly generated data, we test the validity of our solution approaches. Furthermore, using real data from the state of Alabama, we provide recommendations for (i) critical levels of coverage; (ii) factors influencing the service measures; and (iii) dynamic changes in routes.     

A metaheuristic approach to the reliable location routing problem under disruptions

This paper examines a reliable capacitated location–routing problem in which depots are randomly disrupted. Customers whose depots fail must be reinserted into the routes of surviving depots. We present a scenario-based mixed-integer programming model to optimize depot location, outbound delivery routing, and backup plans. We design a metaheuristic algorithm that is based on a maximum-likelihood sampling method, route-reallocation improvement, two-stage neighborhood search and simulated annealing. Numerical tests show that the heuristic is able to generate results that would keep operating costs and failure costs well balanced. Managerial insights on scenario identification, facility deployment and model simplification are drawn.     

The split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem, a fleet of vehicles must service the demands of customers in a least-cost way. By allowing multiple vehicles to service the same customer (i.e., splitting deliveries), substantial savings in travel costs are possible. However, split deliveries are often an inconvenience to the customer who would prefer to have demand serviced in a single visit. We consider the vehicle routing problem in which split deliveries are allowed only if a minimum fraction of a customer’s demand is serviced by a vehicle. We develop a heuristic method for solving this problem and report computational results on a wide range of problem sets.     

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 multi-objective healthcare inventory routing problem; a fuzzy possibilistic approach

This paper presents a new multi-objective mathematical model to address a Healthcare Inventory Routing Problem (HIRP) for medicinal drug distribution to healthcare facilities. The first part of objective function minimizes total inventory and transportation costs, while satisfaction is maximized by minimizing forecast error which caused by product shortage and the amount of expired drugs; Greenhouse Gas (GHG) emissions are also minimized. A demand forecast approach has been integrated into the mathematical model to decrease drug shortage risk. A hybridized possibilistic method is applied to cope with uncertainty and an interactive fuzzy approach is considered to solve an auxiliary crisp multi-objective model and find optimized solutions.     

An exact solution approach for vehicle routing and scheduling problems with soft time windows

A new column generation based exact optimization approach for the vehicle routing and scheduling problem with semi soft time windows (VRPSSTW) is presented. Elementary shortest path problem with resource constraints and late arrival penalties is solved as a subproblem, which rises from the Dantzig–Wolfe decomposition method. Exact solutions of VRPSSTW and hard time windows variant are compared on Solomon’s benchmark instances as well as on an instance based on Tokyo road network. It was found that the VRPSSTW solution results in fewer routes thus overall costs are reduced and late arrival penalties contribute only a small fraction to total cost.     

Containership routing with time deadlines and simultaneous deliveries and pick-ups

In this paper we seek to determine optimal routes for a containership fleet performing pick-ups and deliveries between a hub and several spoke ports. A capacitated vehicle routing problem with pick-ups, deliveries and time deadlines is formulated and solved using a hybrid genetic algorithm for establishing routes for a dedicated containership fleet. Results on the performance of the algorithm and the feasibility of the approach show that a relatively small fleet of containerships could provide efficient services within deadlines. Moreover, through sensitivity analysis we discuss performance robustness and consistency of the developed algorithm under a variety of problem settings and parameters values.     

Task selection and routing problems in collaborative truckload transportation

This paper introduces the task selection and routing problem in collaborative transportation in which a truckload carrier receives tasks from shippers and other partners and makes a selection between a private vehicle and an external carrier to serve each task. The objective is to minimize the variable and fixed costs for operating the private fleet plus the total costs charged by the external carrier. The mathematical formulation and the lower bound are established. A memetic algorithm is developed to solve the problem. The computational results show that the proposed algorithm is effective and efficient.     

An effective genetic algorithm for the fleet size and mix vehicle routing problems

This paper studies the fleet size and mix vehicle routing problem (FSMVRP), in which the fleet is heterogeneous and its composition to be determined. We design and implement a genetic algorithm (GA) based heuristic. On a set of twenty benchmark problems it reaches the best-known solution 14 times and finds one new best solution. It also provides a competitive performance in terms of average solution.     

Models for relief routing: Equity, efficiency and efficacy

In humanitarian relief operations, vehicle routing and supply allocation decisions are critically important. Similar routing and allocation decisions are studied for commercial settings where efficiency, in terms of minimizing cost, is the primary objective. Humanitarian relief is complicated by the presence of multiple objectives beyond minimizing cost. Routing and allocation decisions should result in quick and sufficient distribution of relief supplies, with a focus on equitable service to all aid recipients. However, quantifying such goals can be challenging. In this paper, we define and formulate performance metrics in relief distribution. We focus on efficacy (i.e., the extent to which the goals of quick and sufficient distribution are met) and equity (i.e., the extent to which all recipients receive comparable service). We explore how efficiency, efficacy, and equity influence the structure of vehicle routes and the distribution of resources. We identify trends and routing principles for humanitarian relief based on the analytical properties of the resulting problems and a series of computational tests.     

Capacity dynamics and the formulation of the airport capacity/stability paradox: A European perspective

Access to capacity is often considered to be uncertain, causing airlines to build buffer times into their flight schedules in anticipation of potential delays. Similarly, air navigation service providers use capacity buffers to overcome potential safety standard violations. However, the use of excessive buffers is detrimental to cost efficiency in the air transport system. This paper improves our understanding of capacity predictability. The concepts of capacity dynamics and stability are taken as integral parts of an airport's plan to mitigate the risk of capacity degradation. Based on the concepts of capacity dynamics and stability, the capacity/stability paradox is introduced and discussed.     

Intermodal routing of Canada–Mexico shipments under NAFTA

This paper obtains the optimal routings for intermodal containerized transport from Canada to Mexico. Such traffic is being stimulated by the North American Free Trade Agreement (NAFTA), but the cost and lead times of feasible routes are not well known. We summarize the links and routes to Mexico on which one or more carriers now operate, and then determine non-dominated tradeoffs between cost and service. Every southbound route from Canada requires a transshipment point in the southern or southwestern U. S. Feasible transshipment points are also candidate locations for a manufacturing ‘twin plant’, a distribution centre, or a transportation hub. Here, as a first step in this bigger problem, a network is constructed between five Canadian origins and three important Mexican destinations. Each link employs available intermodal services whose transit time and transportation cost are obtained through industry sources. A shortest-path algorithm enables calculation of the route requiring least time and the route of minimum cost. Non-dominated time/cost tradeoffs are identified for each origin–destination pair. After including inventory expenses (by parametrizing the unit value of lead time), total-cost curves then eliminate some routing alternatives. Guidelines are provided on the effects of mode, carrier, and O–D locations on selection of intermodal routes to Mexico. Finally, two new intermodal services are proposed and their benefits discussed.     

Dynamic routing of time-sensitive air cargo using real-time information

The route planning of time-sensitive air-cargo is becoming more important with the growing air-network congestion and delays. We consider a freight forwarder’s routing of a time-sensitive air-cargo in the presence of real-time and historical information regarding flight availability, departure delays and travel times. A departure delay estimation model is developed to account for real-time information inaccuracy. A novel Markov decision model is formulated and solved with online backward induction. Through synthetic experiments and case studies, we demonstrate that dynamic routing with real-time information can improve delivery reliability and reduce expected cost.     

A vehicle routing cost evaluation algorithm for the strategic analysis of radial distribution networks

This article presents a new algorithm, based on bin packing algorithms, that determines vehicle routing costs on networks with certain geographic characteristics. Requiring very little data and computation time, the algorithm is used to test the impact of adding flexibility to a retailer’s Canadian distribution operations. It is shown that it is possible to save 5–10% of vehicle routing costs by modifying shipping schedules.     

Incorporating location,routing and inventory decisions in supply chain network design

This paper for the first time presents a novel model to simultaneously optimize location, allocation, capacity, inventory, and routing decisions in a stochastic supply chain system. Each customer’s demand is uncertain and follows a normal distribution, and each distribution center maintains a certain amount of safety stock. To solve the model, first we present an exact solution method by casting the problem as a mixed integer convex program, and then we establish a heuristic method based on a hybridization of Tabu Search and Simulated Annealing. The results show that the proposed heuristic is considerably efficient and effective for a broad range of problem sizes.     

A study of the airline boarding problem

The airline industry is currently under intense pressure to simultaneously increase efficiency, customer satisfaction, and profitability. The boarding process is one way to achieve this objective as it lends itself to adaptive changes. The purpose of this paper is to determine the most cost-effective way to board passengers and still maintain quality and customer satisfaction. We conclude that the best strategy is to use a non-traditional methodology of outside-in or some modification thereof. The findings suggest that airline managers should consider issues related to evenly distributing boarding activity throughout the aircraft, developing more effective policies for managing carry-on luggage, and using simultaneous loading through two doors.     

The potential of optimization in communal routing problems: case studies from Finland

In many European countries, municipalities offer their inhabitants a wide variety of social services. In this paper we will focus on efficiently scheduling home care, transportation of the elderly, and home meal delivery. These so-called municipal or communal routing problems can be modeled as different variants of the vehicle routing problem, a well-known optimization problem from the literature. We present a focused literature review and report on case studies using Finnish data. The computational results show that there is a significant potential for cost savings for all applications considered.     

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.