Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.     

A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongoing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.     

Truck dock assignment problem with operational time constraint within crossdocks

In this paper, we consider a truck dock assignment problem with an operational time constraint in crossdocks where the number of trucks exceeds the number of docks available. The problem feasibility is affected by three factors: the arrival and departure time window of each truck, the operational time for cargo shipment among the docks, and the total capacity available to the crossdock. The objective is to find an optimal assignment of trucks that minimizes the operational cost of the cargo shipments and the total number of unfulfilled shipments at the same time. We combine the above two objectives into one term: the total cost, a sum of the total dock operational cost and the penalty cost for all the unfulfilled shipments. The problem is then formulated as an integer programming (IP) model. We find that as the problem size grows, the IP model size quickly expands to an extent that the ILOG CPLEX Solver can hardly manage. Therefore, two meta-heuristic approaches, Tabu Search (TS) and genetic algorithm (GA), are proposed. Computational experiments are conducted, showing that meta-heuristics, especially the Tabu search, dominate the CPLEX Solver in nearly all test cases adapted from industrial applications.     

Supply chain scheduling with receiving deadlines and non-linear penalty

We study the operations scheduling problem with delivery deadlines in a three-stage supply chain process consisting of (1) heterogeneous suppliers, (2) capacitated processing centres (PCs), and (3) a network of business customers. The suppliers make and ship semi-finished products to the PCs where products are finalized and packaged before they are shipped to customers. Each business customer has an order quantity to fulfil and a specified delivery date, and the customer network has a required service level so that if the total quantity delivered to the network falls below a given targeted fill rate, a non-linear penalty will apply. Since the PCs are capacitated and both shipping and production operations are non-instantaneous, not all the customer orders may be fulfilled on time. The optimization problem is therefore to select a subset of customers whose orders can be fulfilled on time and a subset of suppliers to ensure the supplies to minimize the total cost, which includes processing cost, shipping cost, cost of unfilled orders (if any), and a non-linear penalty if the target service level is not met. The general version of this problem is difficult because of its combinatorial nature. In this paper, we solve a special case of this problem when the number of PCs equals one, and develop a dynamic programming-based algorithm that identifies the optimal subset of customer orders to be fulfilled under each given utilization level of the PC capacity. We then construct a cost function of a recursive form, and prove that the resulting search algorithm always converges to the optimal solution within pseudo-polynomial time. Two numerical examples are presented to test the computational performance of the proposed algorithm.     

有时间窗的车辆路径问题的局部下降搜索算法

介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.     

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.     

The transportation problem with exclusionary side constraints

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate within a constant factor (unless P = NP). This research was partially supported by FWO Grant No. G.0114.03.     

An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

This paper presents the case study of an Italian carrier, Grendi Trasporti Marittimi, which provides freight transportation services by trucks and containers. Its trucks deliver container loads from a port to import customers and collect container loads from export customers to the same port. In this case study, all import customers in a route must be serviced before all export customers, each customer can be visited more than once and containers are never unloaded or reloaded from the truck chassis along any route. We model the problem using an Integer Linear Programming formulation and propose an Adaptive Guidance metaheuristic. Our extensive computational experiments show that the adaptive guidance algorithm is capable of determining good-quality solutions in many instances of practical or potential interest for the carrier within 10?min of computing time, whereas the mathematical formulation often fails to provide the first feasible solution within 3?h of computing time.     

A stochastic dynamic traveling salesman problem with hard time windows

Just-in-time (JIT) trucking service, i.e., arriving at customers within specified time windows, has become the norm for freight carriers in all stages of supply chains. In this paper, a JIT pickup/delivery problem is formulated as a stochastic dynamic traveling salesman problem with time windows (SDTSPTW). At a customer location, the vehicle either picks up goods for or delivers goods from the depot, but does not provide moving service to transfer goods from one location to another. Such routing problems are NP-hard in deterministic settings, and in our context, complicated further by the stochastic, dynamic nature of the problem. This paper develops an efficient heuristic for the SDTSPTW with hard time windows. The heuristic is shown to be useful both in controlled numerical experiments and in applying to a real-life trucking problem.     

Recent progress of local search in handling the time window constraints of the vehicle routing problem

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.     

Recent progress of local search in handling the time window constraints of the vehicle routing problem

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

An efficient mixed integer programming model for pairing containers in inland transportation based on the assignment of orders

The inland transportation takes a significant portion of the total cost that arises from intermodal transportation. In addition, there are many parties (shipping lines, haulage companies, customers) who share this operation as well as many restrictions that increase the complexity of this problem and make it NP-hard. Therefore, it is important to create an efficient strategy to manage this process in a way to ensure all parties are satisfied. This paper investigates the pairing of containers/orders in drayage transportation from the perspective of delivering paired containers on 40-ft truck and/or individual containers on 20-ft truck, between a single port and a list of customer locations. An assignment mixed integer linear programming model is formulated, which solves the problem of how to combine orders in delivery to save the total transportation cost when orders with both single and multiple destinations exist. In opposition to the traditional models relying on the vehicle routing problem with simultaneous pickups and deliveries and time windows formulation, this model falls into the assignment problem category which is more efficient to solve on large size instances. Another merit for the proposed model is that it can be implemented on different variants of the container drayage problem: import only, import–inland and import–inland–export. Results show that in all cases the pairing of containers yields less cost compared to the individual delivery and decreases empty tours. The proposed model can be solved to optimality efficiently (within half hour) for over 300 orders.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

A heuristic solution technique to attain the minimal total cost bounds of transporting a homogeneous product with varying demands and supplies

Transportation of a product from multi-source to multi-destination with minimal total transportation cost plays an important role in logistics and supply chain management. Researchers have given considerable attention in minimizing this cost with fixed supply and demand quantities. However, these quantities may vary within a certain range in a period due to the variation of the global economy. So, the concerned parties might be more interested in finding the lower and the upper bounds of the minimal total costs with varying supplies and demands within their respective ranges for proper decision making. This type of transportation problem has received attention of only one researcher, who formulated the problem and solved it by LINGO. We demonstrate that this method fails to obtain the correct upper bound solution always. Then we extend this model to include the inventory costs during transportation and at destinations, as they are interrelated factors. The number of choices of supplies and demands within their respective ranges increases enormously as the number of suppliers and buyers increases. In such a situation, although the lower bound solution can be obtained methodologically, determination of the upper bound solution becomes an NP hard problem. Here we carry out theoretical analyses on developing the lower and the upper bound heuristic solution techniques to the extended model. A comparative study on solutions of small size numerical problems shows promising performance of the current upper bound technique. Another comparative study on results of numerical problems demonstrates the effect of inclusion of the inventory costs.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

A robust optimization approach to dispatching technicians under stochastic service times

We consider the problem of dispatching technicians to service/repair geographically distributed equipment. This problem can be cast as a vehicle routing problem with time windows, where customers expect fast response and small delays. Estimates of the service time, however, can be subject to a significant amount of uncertainty due to misdiagnosis of the reason for failure or surprises during repair. It is therefore crucial to develop routes for the technicians that would be less sensitive to substantial deviations from estimated service times. In this paper we propose a robust optimization model for the vehicle routing problem with soft time windows and service time uncertainty and solve real-world instances with a branch and price method. We evaluate the efficiency of the approach through computational experiments on real industry routing data.     

The open vehicle routing problem with time windows

In this paper, we consider the open vehicle routing problem with time windows (OVRPTW). The OVRPTW seeks to find a set of non-depot returning vehicle routes, for a fleet of capacitated vehicles, to satisfy customers’ requirements, within fixed time intervals that represent the earliest and latest times during the day that customers’ service can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns. The model is solved using a greedy look-ahead route construction heuristic algorithm, which utilizes time windows related information via composite customer selection and route-insertion criteria. These criteria exploit the interrelationships between customers, introduced by time windows, that dictate the sequence in which vehicles must visit customers. Computational results on a set of benchmark problems from the literature provide very good results and indicate the applicability of the methodology in real-life routing applications.     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

Optimizing Supply Shortage Decisions in Base Stock Distribution Operations

This paper addresses policies and agreements between suppliers and customers for handling supply shortages in base-stock systems under uncertain demand. We investigate the impacts that backlogging and expediting decisions have on inventory and transportation costs in these systems and develop a model for deciding whether a supplier should completely backlog, completely expedite, or employ some combination of backlogging and expediting shortages. Our results indicate that practical cases exist where some combination of both expediting and backlogging supply shortages outperforms either completely expediting or backlogging all shortages. Including transportation costs in our model provides incentive to employ `hybrid' policies that partially expedite and partially backlog excess demands within a given period. Our model demonstrates how inventory policy decisions directly impact transportation costs and provides a heuristic approach for jointly minimizing expected inventory and transportation costs.