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.     

Multi-period heterogeneous vehicle routing considering carbon emission trading

This study considers the problem of determining heterogeneous vehicle routes in each period of a given planning horizon while satisfying service combinations, customer demands and vehicle capacities. The objective is to minimize the sum of vehicle operation costs and carbon emission trading cost/benefit, where the trading cost is incurred to purchase the carbon emission right if the total emission exceeds an upper limit in each period, while the trading benefit can be obtained by selling the right in each period, otherwise. A mixed integer programming model is developed to formulate the problem mathematically. Then, a tabu search algorithm is proposed that incorporates the characteristics of the heterogeneous and the period vehicle routing problems while considering the amount of carbon emission in each period. Computational experiments were done on modified benchmark instances and additional random instances, and the results show that the multi-period approach outperforms the existing single-period one in overall average. In particular, the test results show that the multi-period approach can reduce carbon emission more significantly than the single-period one without sacrificing the total cost.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Vehicle routing optimization with soft time windows in a fuzzy random environment

This paper is concerned with a vehicle routing problem with soft time windows (VRPSTW) in a fuzzy random environment. Two objectives are considered: (1) minimize the total travel cost and (2) maximize the average satisfaction level of all customers. After setting up the model for the VRPSTW in a fuzzy random environment, the fuzzy random expected value concept is used to deal with the constraints and its equivalent crisp model is derived. The global–local–neighbor particle swarm optimization with exchangeable particles (GLNPSO-ep) is employed to solve the equivalent crisp model. A case study is also presented to illustrate the effectiveness of the proposed approach.     

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.     

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.     

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.     

Sustainable hub location under mixed uncertainty

This paper addresses a novel sustainable hub location problem (SHLP) in which two new environmental-based cost functions accounting for air and noise pollution of vehicles are incorporated. To cope with uncertain data incorporated in the model, a mixed possibilistic–stochastic programming approach is proposed to construct the crisp counterpart. A simulated annealing (SA) and an imperialist competitive algorithm (ICA) with a new solution representation are developed to solve real-sized instances whose performances are compared with a proposed lower bound. Finally, some computational experiments are provided to demonstrate the effectiveness of the proposed model and solution approaches.     

Benefits of in-vehicle consolidation in less than truckload freight transportation operations

Researchers and public agencies have proposed consolidation policies as an alternative to increase truck payload utilization and mitigate externalities produced by freight transportation. Understanding and enhancing the economic mechanisms that lead to freight consolidation can ease the implementation of these strategies, increase profits for shippers and carriers, and reduce freight-related negative externalities. An important mechanism that has recently been studied for cost reduction in the freight industry is combinatorial auctions. In these auctions, a shipper invites a set of carriers to submit bids for freight lane contracts. Carriers can bid for individual lanes or bundles of them according to their operational characteristics. These bids are constructed considering direct shipments (Truckload operations) and several biding advisory models have been proposed for this purpose. However, there are economies of scale that can be achieved if shipments are consolidated inside vehicles, which have not been explored in the construction of competitive bids. This paper investigates such benefits and provides insights on the competitiveness and challenges associated to the development of consolidated bids (suitable for Less-Than-Truckload operations). Consolidated bids are constructed using a multi-commodity one-to-one pickup-and-delivery vehicle routing problem that is solved using a branch-and-price algorithm. The numerical experiment shows that non-consolidated bids are dominated by consolidated bids, which implies that this type of operation can increase the likelihood of a carrier to win auctioned lanes, while increasing its profits margins over truckload companies (non-consolidated bids), and keeping the reported benefits that combinatorial auctions represent for shippers.     

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.     

Hierarchical multi-objective evacuation routing in stadium using ant colony optimization approach

Evacuation planning is a fundamental requirement to ensure that most people can be evacuated to a safe area when a natural accident or an intentional act happens in a stadium environment. The central challenge in evacuation planning is to determine the optimum evacuation routing to safe areas. We describe the evacuation network within a stadium as a hierarchical directed network. We propose a multi-objective optimization approach to solve the evacuation routing problem on the basis of this hierarchical directed network. This problem involves three objectives that need to be achieved simultaneously, such as minimization of total evacuation time, minimization of total evacuation distance and minimal cumulative congestion degrees in an evacuation process. To solve this problem, we designed a modified ant colony optimization (ACO) algorithm, implemented it in the MATLAB software environment, and tested it using a stadium at the Wuhan Sports Center in China. We demonstrate that the algorithm can solve the problem, and has a better evacuation performance in terms of organizing evacuees’ space-time paths than the ACO algorithm, the kth shortest path algorithm and the second generation of non-dominated sorting genetic algorithm were used to improve the results from the kth shortest path algorithm.     

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.     

Bi-objective bilevel optimization of distribution center locations considering user equilibria

We propose a bi-objective, bilevel optimization model for the location of relief distribution centers (DCs) in humanitarian logistics. The upper-level decision-maker (an aid-providing organization) selects locations for capacitated DCs. On the lower level, beneficiaries choose a DC according to distance and amount of supply to be expected. This effects a user equilibrium on the lower decision level. Upper level objectives are to minimize total opening cost for the DCs and total uncovered demand. We develop an exact algorithm for determining the Pareto frontier of the problem, integrating the adaptive epsilon-constraint method, a branch-and-bound procedure, and the Frank–Wolfe procedure.     

应急物流配送问题的蚁群聚类算法研究

提出了一种用于解决突发事件下,物流配送多目标优化问题的蚁群聚类优化算法。突发事件下的物流配送规划一般包含两方面内容,将救灾物资运往受灾地区和将灾区的伤员及时送至各医疗点。将多目标问题转化为单目标问题,结合蚁群的墓地构造行为特点,利用改进LF蚁群聚类模型,以节点需求未得到满足的不满意度最小和路由时间最短为优化目标,用LF蚁群聚类方法按约束条件进行聚类,最终确定车辆路由线路。