Hybrid metaheuristic solutions to inventory location routing problem

This paper considers a supply chain network with multiple depots and geographically dispersed customers, each of which faces non-constant demand over a discrete planning horizon. The goal is to determine a set of depots to open, the delivery quantities to customers per period and the sequence in which they are replenished by a vehicle fleet such that the total system-wide cost is minimized. To solve it, first we construct a mixed integer program, and then propose a hybrid metaheuristic consisting of initialization, intensification and post-optimization. Results show that the proposed heuristic is considerably efficient and effective for many classical instances.     

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.     

Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost

The vehicle routing problem (VRP) with stochastic demands and weight-related cost is an extension of the VRP. Although some researchers have studied the VRP with either stochastic demands or weight-related cost, the literature on this problem is quite limited. We adopt the a priori optimization to tackle this problem and propose a dynamic programming to compute the expected cost of each route. We develop the adaptive large neighborhood search heuristics equipped with several approximate methods for the problem. To evaluate our heuristics, we generate 84 test instances. Computational results demonstrate the performance of our heuristics and can serve as benchmarks for future researchers.     

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.     

Scenario tree airline fleet planning for demand uncertainty

This paper proposes an innovative multi-period modeling approach to solve the airline fleet planning problem under demand uncertainty. The problem is modeled using a scenario tree approach. The tree is composed of nodes, which represent points of decision in multiple time stages of the planning horizon, and branches, representing demand variation scenarios. The branches link the decision nodes in consequent time stages and compose scenario paths. Fleet decisions are modeled according to these scenario paths, resembling the real-life process in which fleet plans are not defined in a single moment but instead are adjusted according to the demand development. Given that some scenario paths share common decision nodes, decisions among scenarios need to be synchronized. A mixed-integer linear programming model is proposed to determine the ideal fleet composition for each scenario in the tree and to describe this interdependency between scenarios. Considering the probability of a scenario, fleet composition probabilities for each time-period can be determined. Two real-world based case studies are performed to show the validity of the model. Results show that the proposed scenario tree approach can provide flexible multi-period airline fleet plans, which are more robust to future demand scenarios than fleet solutions obtained using the traditional approach of considering a single deterministic demand evolution scenario.     

Arc routing problems to restore connectivity of a road network

After a disaster, restoring accessibility in the affected area is critical for response operations. We study two arc routing problems for clearing blocked roads. The first problem minimizes the time to reconnect the road network, while the second maximizes the total benefit gained by reconnecting network components within a time limit. For each problem, we develop a mixed integer programming formulation and two versions of a heuristic algorithm. We conduct computational experiments on Istanbul data and instances adapted from the literature. The heuristics achieve near-optimal or optimal solutions quickly in most of the tested instances.     

Mixed truck delivery systems with both hub-and-spoke and direct shipment

This paper studies a mixed truck delivery system that allows both hub-and-spoke and direct shipment delivery modes. A heuristic algorithm is developed to determine the mode of delivery for each demand and to perform vehicle routing in both modes of deliveries. Computational experiments are carried out on a large set of randomly generated problem instances to compare the mixed system with the pure hub-and-spoke system and the pure direct shipment system. The experiment results show that the mixed system can save around 10% total traveling distance on average as compared with either of the two pure systems.     

Fair profit contract for a carrier collaboration framework in a green hub network under soft time-windows: Dual lexicographic max–min approach

This paper models a novel and practical bi-objective hub-location problem under a centralized carrier collaboration framework between one holding company and multiple carriers. The holding company first establishes a hub-and-spoke network in order to locate p hubs and to assign the center nodes to the located hubs. Then, it allocates the transportation routes of the hub network to the carriers. In contrast, the carriers should select an appropriate vehicle type to serve the transportation requests in a green hub network. The carriers are also able to meet the transportation requests within a certain time-window based on a soft time-window mechanism. Moreover, aiming to emphasize green transportation, a vehicle emission model is used to take into account CO₂ emissions of the vehicles where the fuel consumption is a function of speed level. Aiming to identify a win–win deal between the holding company and the carriers, a dual lexicographic max–min (LMM) approach is used in order to optimize their profits in a fair way. Finally, some numerical experiments are presented to demonstrate the applicability of the proposed methodology. The computational results show that not only the holding company and the carriers can better generate a fair profit contract among themselves using the LMM approach, but also both can obtain more profit in the worst case for their businesses rather than using the max–min approach. In addition, sensitivity analyses show that increasing the size of the soft time-window leads to a reduction in the delivery schedule violations, while results in raising the total profit. Moreover, the tax cost of fuel consumption as well as the number of potential vehicles has a substantial impact on both the fuel consumption and carrier’s profit.     

A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph

We study a time-constrained heterogeneous vehicle routing problem on a multigraph where parallel arcs between pairs of vertices represent different travel options based on criteria such as time, cost, and distance. We formulate the problem as a mixed-integer linear programming model and develop a tabu search heuristic that efficiently addresses computational challenges due to parallel arcs. Numerical experiments show that the heuristic is highly effective and that freight operators can achieve advantages in cost and customer service by considering alternative paths, especially when route duration limits are restrictive and/or when vehicles of smaller capacity are dispatched to serve remote customers.     

A top-down approach and a decision support system for the design and management of logistic networks

This paper presents an original top-down approach, made of original models and solving methods, and a decision support system (DSS) for the execution of the strategic planning, the tactical planning and the operational planning in a multi-echelon multi-stage multi-commodity and multi-period production, distribution and transportation system. The DSS is a software platform useful for the design, management and control of real instances. It can efficiently supports the decision making process of logistic managers and planners of large enterprises as multi-facilities companies and production–distribution networks. A significant case study is illustrated. The results obtained by the application of different problem settings are compared and discussed.     

A top-down approach and a decision support system for the design and management of logistic networks

This paper presents an original top-down approach, made of original models and solving methods, and a decision support system (DSS) for the execution of the strategic planning, the tactical planning and the operational planning in a multi-echelon multi-stage multi-commodity and multi-period production, distribution and transportation system. The DSS is a software platform useful for the design, management and control of real instances. It can efficiently supports the decision making process of logistic managers and planners of large enterprises as multi-facilities companies and production–distribution networks. A significant case study is illustrated. The results obtained by the application of different problem settings are compared and discussed.     

Multi-objective design of an organ transplant network under uncertainty

We propose a novel multi-period location–allocation model for the design of an organ transplant transportation network under uncertainty. The model consists of a bi-objective mathematical programming model that minimizes total cost and time, including waiting time in the queue for the transplant operation, while considering organs’ priorities. A fuzzy multi-objective programming based approach is presented to solve the small and medium size problems to optimality. For larger problems, we propose two meta-heuristics based algorithms. Lower bounds, and several numerical examples with managerial insights are discussed. A real case-study is provided, and the existing and the proposed optimal solutions are compared.     

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.     

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.     

Joint planning of berth and yard allocation in transshipment terminals using multi-cluster stacking strategy

In this work, a joint planning problem for berth and yard allocation in transshipment terminals is addressed. Multi-cluster stacking strategy is proposed to split each transshipment flow into a number of container clusters and then stack each cluster in different yard blocks. A mixed integer quadratic programming model is formulated to minimize the total distance of exchanging containers between mother vessels and feeders, and the workload imbalance among yard blocks. A novel three-stage heuristic solution approach is developed and extensive numerical experiments are conducted to show the effectiveness of the proposed approach and the benefit of the multi-cluster strategy.     

A novel methodology for designing a household waste collection system for insular zones

This paper addresses the problem of designing a household waste collection system for rural insular areas using a barge for transportation, based on a novel mixed integer programming model that simultaneously integrates decisions of waste collection sites selection within the islands to be served, visit schedule for each selected collection site, and multi-period vehicle routing. An application to a real-world instance consisting of small rural islands located in the south of Chile shows the effectiveness and complexity of the model, along with the advantages of using a waste compactor instead of transporting the waste using bins onboard a barge.     

Robust planning and disruption management in roll-on roll-off liner shipping

This paper presents different strategies for handling disruptions in fleet deployment in roll-on roll-off liner shipping, which basically consists of assigning a fleet of vessels to predefined voyages at minimum cost. A new mathematical model of the problem is presented, including a set of robust planning strategies, such as adding slack and rewarding early arrivals. To solve real-life instances a rolling horizon heuristic is proposed. A computational study, where we also propose some recovery planning strategies, is conducted, and simulation results show that adding robustness significantly reduces the actual cost of the plan and the total delays of the voyages.     

Pareto efficient allocation of an in-motion wireless charging infrastructure for electric vehicles in a multipath network

Electric vehicles (EV) use an eco-friendly technology that limits the greenhouse gas emissions of the transport sector, but the limited battery capacity and the density of the battery are the major barriers to the widespread adoption of EV. To mitigate this, a good method seems to be the innovative wireless charging technology called ‘On-Line EV (OLEV)’, which is a contactless electric power transfer technology. This EV technology has the potential to charge the vehicle’s battery dynamically while the vehicle is in motion. This system helps to reduce not only the size of the battery but also its cost, and it also contributes to extending the driving range before the EV has to stop. The high cost of this technology requires an optimal location of the infrastructure along the route. For this reason, the objective of this paper is to study the problem of the location of the wireless charging infrastructure in a transport network composed of multiple routes between the origin and the destination. To find a strategic solution to this problem, we first and foremost propose a nonlinear integer programming solution to reach a compromise between the cost of the battery, which is related to its capacity, and the cost of installing the power transmitters, while maintaining the quality of the vehicle’s routing. Second, we adapt the multi-objective particle swarm optimization (MPSO) approach to our problem, as the particles were robust in solving nonlinear optimization problems. Since we have a multi-objective problem with two binary variables, we combine the binary and discrete versions of the particle swarm optimization approach with the multi-objective one. The port of Le Havre is presented as a case study to illustrate the proposed methodology. The results are analyzed and discussed in order to point out the efficiency of our resolution method.     

A novel mathematical model for a multi-period,multi-product optimal ordering problem considering expiry dates in a FEFO system

One of the main challenges of retail units is to determine the order quantities of different types of products, each with a specific expiry date, so that the system cost including shortage cost is minimized. We study a new multi-product multi-period replenishment problem for a First Expired-First Out (FEFO) based warehouse management system. The proposed nonlinear model is first converted to a linear one and then solved by applying two evolutionary algorithms: the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), in which design parameters are set using Taguchi method. Computational results demonstrate the applicability of the proposed model for perishable items and comparing the results shows the efficiency of the proposed metaheuristics as well.     

Combining service frequency and vehicle routing for managing supplier shipments

This paper proposes a new approach to designing inbound material collection routes that considers pick-up frequency and spatial design as joint decisions to minimize total logistics (transportation plus inventory) cost. The clustering-based optimization uses an approximation to the actual cost of a routing solution without actual route construction. We show that the problem is analogous to a single-source fixed-charge facility location problem, and near-optimal solutions can be found using an efficient heuristic algorithm. Tests show the effectiveness of how this model is formulated and a case study demonstrates that substantial total cost savings can be achieved in realistic applications.