Dynamic scheduling of recreational rental vehicles with revenue management extensions

The rental fleet scheduling problem (RFSP) arises in vehicle-rental operations that offer a wide variety of vehicle types to customers, and allow a rented vehicle to ‘migrate’ to a setdown depot other than the pickup depot.When there is a shortage of vehicles of a particular type at a depot, vehicles may be relocated to that depot, or vehicles of similar types may be substituted.The RFSP involves assigning vehicles to rentals so as to minimise the costs of these operations, and arises in both static and online contexts. The authors have adapted a well-known assignment algorithm for application in the online context. In addition, a network-flow algorithm with more comprehensive coverage of problem conditions is used to investigate the determination of rental pricing using revenue management principles. The paper concludes with an outline of the algorithms’ use in supporting the operations of a large recreational vehicle rental company.     

Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

An interactive,computer-aided ship scheduling system

This paper is concerned with a fleet scheduling and inventory resupply problem faced by an international chemical operation. The firm uses a fleet of small ocean-going tankers to deliver bulk fluid to warehouses all over the world. The scheduling problem centers around decisions on routes, arrival/departure times, and inventory replenishment quantities. An interactive computer system was developed and implemented at the firm, and was successfully used to address daily scheduling issues as well as longer range planning problems. The purpose of this paper is to first present how the underlying decision problem was analyzed using both a network flow model and a mixed integer programming model, and then to describe the components of the decision support system developed to generate schedules. The use of the system in various decision making applications is also described.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care

This paper addresses a vehicle scheduling problem encountered in home health care logistics. It concerns the delivery of drugs and medical devices from the home care company’s pharmacy to patients’ homes, delivery of special drugs from a hospital to patients, pickup of bio samples and unused drugs and medical devices from patients. The problem can be considered as a special vehicle routing problem with simultaneous delivery and pickup and time windows, with four types of demands: delivery from depot to patient, delivery from a hospital to patient, pickup from a patient to depot and pickup from a patient to a medical lab. Each patient is visited by one vehicle and each vehicle visits each node at most once. Patients are associated with time windows and vehicles with capacity. Two mixed-integer programming models are proposed. We then propose a Genetic Algorithm (GA) and a Tabu Search (TS) method. The GA is based on a permutation chromosome, a split procedure and local search. The TS is based on route assignment attributes of patients, an augmented cost function, route re-optimization, and attribute-based aspiration levels. These approaches are tested on test instances derived from existing VRPTW benchmarks.     

A goal programming approach to vehicle routing problems with soft time windows

The classical vehicle routing problem involves designing a set of routes for a fleet of vehicles based at one central depot that is required to serve a number of geographically dispersed customers, while minimizing the total travel distance or the total distribution cost. Each route originates and terminates at the central depot and customers demands are known. In many practical distribution problems, besides a hard time window associated with each customer, defining a time interval in which the customer should be served, managers establish multiple objectives to be considered, like avoiding underutilization of labor and vehicle capacity, while meeting the preferences of customers regarding the time of the day in which they would like to be served (soft time windows). This work investigates the use of goal programming to model these problems. To solve the model, an enumeration-followed-by-optimization approach is proposed which first computes feasible routes and then selects the set of best ones. Computational results show that this approach is adequate for medium-sized delivery problems.     

A time–space network based exact optimization model for multi-depot bus scheduling

The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and waiting time. This paper discusses the multi-depot, multi-vehicle-type bus scheduling problem (MDVSP), involving multiple depots for vehicles and different vehicle types for timetabled trips. We use time–space-based instead of connection-based networks for MDVSP modeling. This leads to a crucial size reduction of the corresponding mathematical models compared to well-known connection-based network flow or set partitioning models. The proposed modeling approach enables us to solve real-world problem instances with thousands of scheduled trips by direct application of standard optimization software. To our knowledge, the largest problems that we solved to optimality could not be solved by any existing exact approach. The presented research results have been developed in co-operation with the provider of transportation planning software PTV AG. A software component to support planners in public transport was designed and implemented in context of this co-operation as well.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

The static bike relocation problem with multiple vehicles and visits

This paper introduces the static bike relocation problem with multiple vehicles and visits, the objective of which is to rebalance at minimum cost the stations of a bike sharing system using a fleet of vehicles. The vehicles have identical capacities and service time limits, and are allowed to visit the stations multiple times. We present an integer programming formulation, implemented under a branch-and-cut scheme, in addition to an iterated local search metaheuristic that employs efficient move evaluation procedures. Results of computational experiments on instances ranging from 10 to 200 vertices are provided and analyzed. We also examine the impact of the vehicle capacity and of the number of visits and vehicles on the performance of the proposed algorithms.     

The Adult Training Centre Problem: A Case Study

An optimal solution is found to a real-world problem which has the characteristics of a multiple travelling-salesman problem. It deals specifically with methods of obtaining the 'best' routeing for four vehicles which provide a daily service from a depot to 38 locations. The solution technique uses both heuristic and exact algorithms to derive the order for visits to the 38 locations.     

A hybrid tabu search based heuristic for the periodic distribution inventory problem with perishable goods

Most of the research on integrated inventory and routing problems ignores the case when products are perishable. However, considering the integrated problem with perishable goods is crucial since any discrepancy between the routing and inventory cost can double down the risk of higher obsolescence costs due to the limited shelf-life of the products. In this paper, we consider a distribution problem involving a depot, a set of customers and a homogeneous fleet of capacitated vehicles. Perishable goods are transported from the depot to customers in such a way that out-of-stock situations never occur. The objective is to simultaneously determine the inventory and routing decisions over a given time horizon such that total transportation cost is minimized. We present a new “arc-based formulation” for the problem which is deemed more suitable for our new tabu search based approach for solving the problem. We perform a thorough sensitivity analysis for each of the tabu search parameters individually and use the obtained gaps to fine-tune the parameter values that are used in solving larger sized instances of the problem. We solve different sizes of randomly generated instances and compare the results obtained using the tabu search algorithm to those obtained by solving the problem using CPLEX and a recently published column generation algorithm. Our computational experiments demonstrate that the tabu search algorithm is capable of obtaining a near-optimal solution in less computational time than the time required to solve the problem to optimality using CPLEX, and outperforms the column generation algorithm for solving the “path flow formulation” of the problem in terms of solution quality in almost all of the considered instances.     

An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls

In this article, a visual interactive approach based on a new greedy randomised adaptive memory programming search (GRAMPS) algorithm is proposed to solve the heterogeneous fixed fleet vehicle routing problem (HFFVRP) and a new extension of the HFFVRP, which is called heterogeneous fixed fleet vehicle routing problem with backhauls (HFFVRPB). This problem involves two different sets of customers. Backhaul customers are pickup points and linehaul customers are delivery points that are to be serviced from a single depot by a heterogeneous fixed fleet of vehicles, each of which is restricted in the capacity it can carry, with different variable travelling costs.     

A hybrid constraint programming approach to?the?log-truck scheduling problem

Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. This paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. The problem consists of scheduling the transportation of logs between forest areas and woodmills, as well as routing the fleet of vehicles to satisfy these transportation requests. The objective is to minimize the total cost of the non-productive activities such as the waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integer programming model to deal with the optimization of deadheads. Both of these models are combined through the exchange of global constraints. Finally the whole approach is validated on real industrial data.     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

Container fleet-sizing for part transportation and storage in a two-level supply chain

This research addresses the fleet-sizing of containers that are used for the protection, transportation, and storage of parts between a component plant and multiple assembly plants. These containers are needed for the storage of completed parts as they are produced, and also for storage of parts as they are used in assembly. The containers are reusable, expensive, occupy a large amount of space when empty or full, and are required to maintain production. An analytical model is developed for the minimum container fleet size that results in no production stoppages due to lack of containers assuming no system variability. The model considers the discrete nature of part production and shipping as well as differences in available production and transportation time. The model is shown to be accurate and provides insight into the factors that affect container fleet size and production stoppage trade-offs.     

Inventory Positioning in Multiple Product Supply Chains

In this paper we address the problem of inventory positioning, i.e., the determination of the supply chain node where inventory should be held, to minimize holding costs given a pre-specified order fill rate. A single-echelon inventory system with multiple products models the problem. The value of inventory is assumed to be an increasing function of the amount of processing performed at upstream nodes, while achieved fill-rates are dependent on the distance or time between the inventory storage and customer locations. We propose a novel analytical approach to solve the problem for the case of normally distributed demand that is based on iterative calculations of inventory holding costs at the various potential inventory locations.     

Designing multi-vehicle delivery tours in a grid-cell format

This paper presents a methodology to be used in the design of multi-delivery tours associated with the servicing of a heterogeneous region, where the density of visiting points and the amount of cargo vary over the served area. Both vehicle cycle time and vehicle load are treated probabilistically. The region under analysis is partitioned into a number of sectors, rings, and districts, with the polar coordinates centered at the depot. We assume a rectangular grid structure for the representation of the spatial variables. This division is intended to attain a quasi-homogeneous distribution effort (approximate equal number of vehicles) in each partition. The optimization model seeks the best fleet of vehicles that minimizes total daily transport costs. As an example, the model is applied to a parcel delivery problem in the city of São Paulo, Brazil.     

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.     

BoneRoute: An Adaptive Memory-Based Method for Effective Fleet Management

This paper presents an adaptive memory-based method for solving the Capacitated Vehicle Routing Problem (CVRP), called BoneRoute. The CVRP deals with the problem of finding the optimal sequence of deliveries conducted by a fleet of homogeneous vehicles, based at one depot, to serve a set of customers. The computational performance of the BoneRoute was found to be very efficient, producing high quality solutions over two sets of well known case studies examined.