Transportation planning in freight forwarding companies: Tabu search algorithm for the integrated operational transportation planning problem

The integrated operational transportation planning problem extends the traditional vehicle routing and scheduling problem by the possibility of outsourcing a part of the requests by involving subcontractors. The purpose of this paper is to present the integrated planning problem and to propose an approach for solving it by a tabu search heuristic. Existing approaches from literature which discuss vehicle routing combined with outsourcing regard only one specific type of subcontracting. This paper describes and explores the complex situation where an own fleet and several types of subcontracting are used for request fulfillment. As the approach contains new aspects, unknown to the literature so far, tabu search is extended to special types of moves. On the basis of computational results the cost structure is analyzed in order to investigate the long-term planning question whether and to what extend it is profitable to maintain an own fleet.     

Exact algorithms for routing problems under vehicle capacity constraints

The solution of a vehicle routing problem calls for the determination of a set of routes, each performed by a single vehicle which starts and ends at its own depot, such that all the requirements of the customers are fulfilled and the global transportation cost is minimized. The routes have to satisfy several operational constraints which depend on the nature of the transported goods, on the quality of the service level, and on the characteristics of the customers and of the vehicles. One of the most common operational constraint addressed in the scientific literature is that the vehicle fleet is capacitated and the total load transported by a vehicle cannot exceed its capacity.     

Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location and environmental characteristics. This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan, statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet with low emission vehicles are also given. This revised version was published online in August 2006 with corrections to the Cover Date.     

Integrated planning of transportation and recycling for multiple plants based on process simulation

By-products accrue in all stages of industrial production networks. Legal requirements, shortening of primary resources and their increasing prices make their recycling more and more important. For the re-integration into the economic cycle the scope of common supply chain management is enlarged and so-called closed-loop supply chains with adapted and new planning tasks are developed. In process industries this requires a detailed modelling of the recycling processes. This is of special relevance for operational planning tasks in which an optimal usage of a given production system is envisaged. This contribution presents an integrated planning approach for a real-world case study from the zinc industry to achieve such an adequate process modelling. We consider the planning problem of a company that operates four metallurgical recycling plants and has to allocate residues from different sources to these recycling sites. The allocation determines the raw material mix used in the plants. This blending has an effect on the transportation costs and the costs and revenues of the individual technical processes in the recycling plants. Therefore in this problem transportation and recycling planning for multiple sites have to be regarded in an integrated way. The necessary detailed process modelling is achieved by the use of a flowsheet process simulation system to model each recycling plant individually. The models are used to derive linear input–output functions by multiple linear regression analyses. These are used in an integrated planning model to calculate the decision-relevant input and output flows that are dependent upon the allocation of the residues to the recycling sites. The model is embedded in a decision support system for the operational use. An example application and sensitivity analyses demonstrate and validate the approach and its potentials. The approach is transferable to other recycling processes as well as to other processes in process industries.     

Fleet configuration subject to stochastic demand: an application in the distribution of liquefied petroleum gas

We study the problem of configuring a fleet, in which vehicles receive information on-line about the demand that they should fulfil while they are on the road. In each district it must be decided the number of vehicles and their capacity. The objective function is to minimise the operational cost subject to constraints for the minimum delivery capacity, the maximum vehicle size and the average waiting time for customers. The last constraint is modelled as a queuing system that is adjusted according to the simulation of the delivery process of a Chilean company that distributes liquefied petroleum gas in portable cylinders. We provide the analytical form of all the components of the model, so it can be solved using a standard non-linear programming package. We show that the fleet may increase its sales by 3% and reduce the waiting time of customers 10% by allowing a set of vehicles to share the buffer of orders rather than having vehicles to exclusively serve smaller sectors.     

Service network design models for two-tier city logistics

This paper focuses on two-tier city logistics systems for advanced management of urban freight activities and, in particular, on the first layer of such systems where freight is moved from distribution centers on the outskirts of the city to satellite platforms by urban vehicles, from where it will be distributed to customers by a different fleet of dedicated vehicles. We address the issue of planning the services of this first tier system, that is, select services, their routes and schedules, and determine the itineraries of the customer-demand flows through these facilities and services. We propose a general scheduled service network design modelling framework that captures the fundamental concepts related to the definition of urban-vehicle tactical plans within a two-tier distribution network. We examine several operational assumptions regarding the management of the urban-vehicle fleet and the flexibility associated with the delivery of goods, and show how the proposed modelling framework can evolve to represent an increasing level of detail. A discussion of algorithmic perspectives completes the paper.     

Heuristic algorithms for a multi-period multi-stop transportation planning problem

We consider a multi-period multi-stop transportation planning problem (MPMSTP) in a one-warehouse multi-retailer distribution system where a fleet of homogeneous vehicles delivers products from a warehouse to retailers. The objective of the MPMSTP is to minimize the total transportation distance for product delivery over the planning horizon while satisfying demands of the retailers. We suggest two heuristic algorithms based on the column generation method and the simulated annealing algorithm. Computational experiments on randomly generated test problems showed that the suggested algorithms gave better solutions than an algorithm currently used in practice and algorithms modified from existing algorithms for vehicle routing problems.     

The Size and Composition of a Road Transport Fleet

The paper starts with a discussion of the simple fleet size problem. It is shown that this simple problem can be formulated as a linear program.The second part of the paper consists of an actual case study. The fleet concerned is faced with highly seasonal demand which can be met by the firm's own vehicles or by outside hire. There are two types of vehicle, both of which are available in six different sizes. Linear programming was used to find the optimum size and composition of the company fleet. The results, which were substantially implemented, recommended a smaller company fleet and concentration on larger and more flexible vehicles.     

Petrol delivery tanker assignment and routing: a case study in Hong Kong

In this paper, we present a case study on a tanker assignment and routing problem for petrol products in Hong Kong. A fleet of heterogeneous dangerous goods vehicles has been assigned to deliver several types of petroleum products to petrol stations with different tank capacities. Under the vendor-managed inventory system, the delivery company is responsible for controlling the station's inventory and replenishment. The operational characteristics and challenges such as geographic zoning, size of petrol stations, routing restrictions and so on are unique and have been described in this paper. A decision support system (DSS) combining heuristic clustering and optimal routing is employed to find the optimal fleet assignment and routing. Multiple objectives are considered simultaneously such that the number of tankers used could be minimized, the number of drops in trips is minimized, profit in terms of total products delivered is maximized and utilization of resources is maximized. The case illustrates the benefit and advantages of using the proposed DSS.     

Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier

The problem reported in this paper is a variant of the classical vehicle routing problem, where customer requests for a transportation company can be served either by its private fleet of vehicles or assigned to an external common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economical to do so. Accordingly, the objective is to minimize the variable and fixed costs of the private fleet plus the costs charged by the common carrier. A tabu search heuristic with a neighbourhood structure based on ejection chains is proposed to solve this problem. It is empirically demonstrated that this algorithm outperforms the best approaches reported in the literature on a set of benchmark instances with both homogeneous and heterogeneous fleets.     

Column generation based heuristic for tactical planning in multi-period vehicle routing

The periodic vehicle routing problem (PVRP) consists in establishing a planning of visits to clients over a given time horizon so as to satisfy some service level while optimizing the routes used in each time period. The tactical planning model considered here restricts its attention to scheduling visits and assigning them to vehicles while leaving sequencing decisions for an underlying operational model. The objective is twofold: to optimize regional compactness of the routes in a desire to specialize routes to restricted geographical area and to balance the workload evenly between vehicles. Approximate solutions are constructed using a truncated column generation procedure followed by a rounding heuristic. This mathematical programming based procedure can deal with problems with 50–80 customers over five working days which is the range of size of most PVRP instances treated in the literature with meta-heuristics. The paper highlights the importance of alternative optimization criteria not accounted for in standard operational models and provides insights on the implementation of a column generation based rounding heuristic.     

A sweep-based algorithm for the fleet size and mix vehicle routing problem

This paper presents a new sweep-based heuristic for the fleet size and mix vehicle routing problem. This problem involves two kinds of decisions: the selection of a mix of vehicles among the available vehicle types and the routing of the selected fleet. The proposed algorithm first generates a large number of routes that are serviced by one or two vehicles. The selection of routes and vehicles to be used is then made by solving to optimality, in polynomial time, a set-partitioning problem having a special structure. Results on a set of benchmark test problems show that the proposed heuristic produces excellent solutions in short computing times. Having a fast but good solution method is needed for transportation companies that rent a significant part of their fleet and consequently can take advantage of frequent changes in fleet composition. Finally, the proposed heuristic produced new best-known solutions for three of the test problems; these solutions are reported.     

Routing a mix of conventional,plug-in hybrid,and electric vehicles

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric vehicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two engines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost.To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.     

Prototype fleet optimization model

Product development in the automotive industry is a complex process that involves extensive testing of components, subsystems, systems and full vehicles. A fleet of unique individually manufactured vehicles must be built and scheduled amongst different major system activities to be used in comprehensive testing programs. In this paper we present a multi-stage mathematical programming model, set covering plus scheduling, that has been used to restructure the development of the prototype fleet and the assignment of tests to specific vehicles. A basic version of the model implemented on a complex vehicle program produced a 25% reduction in fleet size as compared to the forecast originally made by the company. In addition, the model was the driver for the restructuring of the prototype planning process. In presenting this model, we will describe: (a) the model development process including structuring of the input and output to meet customer needs, (b) model structure, (c) keys to implementation success, and (d) the system's overall impact on the prototype planning process.     

Optimizing fleet size and delivery scheduling for multi-temperature food distribution

In light of the demand for high-quality fresh food, transportation requirements for fresh food delivery have been continuously increasing in urban areas. Jointly delivering foods with different temperature-control requirements is an important issue for urban logistic carriers who transport both low temperature-controlled foods and normal merchandise. This study aims to analyze and optimize medium- and short-term operation planning for multi-temperature food transportation. For medium-term planning, this study optimizes fleet size for carriers considering time-dependent multi-temperature food demand. For short-term planning, this study optimizes vehicle loads and departure times from the terminal for each order of multi-temperature food, taking the fleet size decided during medium-term planning into account. The results suggest that carriers determine departure times of multi-temperature food with demand–supply interaction and deliver food of medium temperature ranges with priority because delivering such food yields more profit.     

A Lagrangian relaxation approach to multi-period inventory/distribution planning

We consider a multi-period inventory/distribution planning problem (MPIDP) in a one-warehouse multiretailer distribution system where a fleet of heterogeneous vehicles delivers products from a warehouse to several retailers. The objective of the MPIDP is to minimise transportation costs for product delivery and inventory holding costs at retailers over the planning horizon. In this research, the problem is formulated as a mixed integer linear programme and solved by a Lagrangian relaxation approach. A subgradient optimisation method is employed to obtain lower bounds. We develop a Lagrangian heuristic algorithm to find a good feasible solution of the MPIDP. Computational experiments on randomly generated test problems showed that the suggested algorithm gave relatively good solutions in a reasonable amount of computation time.     

A two-stage model for a day-ahead paratransit planning problem

We consider a dynamic planning problem for paratransit transportation. The focus is on a decision to take one day ahead: which requests to serve with own vehicles, and which requests to subcontract to taxis? We call this problem the day-ahead paratransit planning problem. The developed model is a non-standard two-stage integer recourse model. Both stages consist of two consecutive optimization problems: the clustering of requests into routes, and the assignment of these routes to vehicles. To solve this model, a genetic algorithm approach is used. Computational results are presented for randomly generated data sets.     

A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints

The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a variant of the classical vehicle routing problem in which customers are served by a heterogeneous fleet of vehicles. These vehicles have different capacities, fixed and variable operating costs, length and width in dimension, and two-dimensional loading constraints. The objective of this problem is to minimize transportation cost of designed routes, according to which vehicles are used, to satisfy the customer demand. In this study, we proposed a simulated annealing with heuristic local search (SA_HLS) to solve the problem and the search was then extended with a collection of packing heuristics to solve the loading constraints in 2L-HFVRP. To speed up the search process, a data structure was used to record the information related to loading feasibility. The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP). In addition, the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.     

Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case

The basic Vehicle Routing Problem (VRP) consists of computing a set of trips of minimum total cost, to deliver fixed amounts of goods to customers with a fleet of identical vehicles. Few papers address the case with several types of vehicles (heterogeneous fleet). Most of them assume an unlimited number of vehicles of each type, to dimension the fleet from a strategic point of view. This paper tackles the more realistic tactical or operational case, with a fixed number of vehicles of each type, and the optional possibility for each vehicle to perform several trips. It describes several heuristics, including a very efficient one that progressively merges small starting trips, while ensuring that they can be performed by the fleet. This heuristic seeks to minimize the number of required vehicles as a secondary objective. It outperforms classical VRP heuristics, can easily handle various constraints, and gives very good initial solutions for a tabu search method. The real case of a French manufacturer of furniture with 775 destination stores is presented.     

Multimodal freight transportation planning: A literature review

Multimodal transportation offers an advanced platform for more efficient, reliable, flexible, and sustainable freight transportation. Planning such a complicated system provides interesting areas in Operations Research. This paper presents a structured overview of the multimodal transportation literature from 2005 onward. We focus on the traditional strategic, tactical, and operational levels of planning, where we present the relevant models and their developed solution techniques. We conclude our review paper with an outlook to future research directions.