Heuristics for the multi-depot petrol station replenishment problem with time windows

In the multi-depot petrol station replenishment problem with time windows (MPSRPTW), the delivery of petroleum products stored in a number of different petroleum depots to a set of petrol distribution stations has to be optimized. Each depot has its own fleet of heterogeneous and compartmented tank trucks. Stations specify their demand by indicating the minimum and maximum quantities to be delivered for each ordered product and require the delivery within a predetermined time window. Several inter-related decisions must be made simultaneously in order to solve the problem. For this problem, the set of feasible routes to deliver all the demands, the departure depot for each route, the quantities of each product to be delivered, the assignment of these routes to trucks, the time schedule for each trip, and the loading of the ordered products to different tanks of the trucks used need to be determined. In this paper, we propose a mathematical model that selects, among a set of feasible trips, the subset that allows the delivery of all the demands while maximizing the overall daily net revenue. If this model is provided with all possible feasible trips, it determines the optimal solution for the corresponding MPSRPTW. However, since the number of such trips is often huge, we developed a procedure to generate a restricted set of promising feasible trips. Using this restricted set, the model produces a good but not necessarily optimal solution. Thus the proposed solution process can be seen as a heuristic. We report the results of the extensive numerical tests carried out to assess the performance of the proposed heuristic. In addition, we show that, for the special case of only one depot, the proposed heuristic outperforms a previously published solution method.     

An exact algorithm for the petrol station replenishment problem

In the petrol station replenishment problem (PSRP), the aim is to deliver petroleum products to petrol stations by means of an unlimited heterogeneous fleet of compartmented tank trucks. The problem consists of jointly determining quantities to deliver within a given interval, of allocating products to tank truck compartments and of designing delivery routes to stations. This article describes an exact algorithm which decomposes the PSRP into a truck loading problem and a routing problem. An algorithm which makes use of assignment, optimality tests and possibly standard ILP algorithm is proposed to solve the loading problem. The routing problem is handled using two different strategies, based either on a matching approach or on a column generation scheme. This algorithm was extensively tested on randomly generated data and on a real-life case arising in Eastern Quebec.     

A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem

This paper considers the mobile facility routing and scheduling problem with stochastic demand (MFRSPSD). The MFRSPSD simultaneously determines the route and schedule of a fleet of mobile facilities which serve customers with uncertain demand to minimize the total cost generated during the planning horizon. The problem is formulated as a two-stage stochastic programming model, in which the first stage decision deals with the temporal and spatial movement of MFs and the second stage handles how MFs serve customer demands. An algorithm based on the multicut version of the L-shaped method is proposed in which several lower bound inequalities are developed and incorporated into the master program. The computational results show that the algorithm yields a tighter lower bound and converges faster to the optimal solution. The result of a sensitivity analysis further indicates that in dealing with stochastic demand the two-stage stochastic programming approach has a distinctive advantage over the model considering only the average demand in terms of cost reduction.     

A (Q, R) inventory replenishment model with two delivery modes

Although splitting shipments across multiple delivery modes typically increases total shipping costs as a result of diseconomies of scale, it may offer certain benefits that can more than offset these costs. These benefits include a reduction in the probability of stockout and in the average inventory costs. We consider a single-stage inventory replenishment model that includes two delivery modes: a cheaper, less reliable mode, and another, more expensive but perfectly reliable mode. The high-reliability mode is only utilized in replenishment intervals in which the lead time of the less-reliable mode exceeds a certain value. This permits substituting the high-reliability mode for safety stock, to some degree. We characterize optimal replenishment decisions with these two modes, as well as the potential benefits of simultaneously using two delivery modes.     

The effect of replenishment policies on the bullwhip effect: A transfer function approach

An important phenomenon in supply chain management, known as the bullwhip effect, suggests that demand variability increases as one moves up a supply chain. This paper examines the influence of different replenishment policies on the occurrence of the bullwhip effect. The paper demonstrates that certain replenishment policies can in themselves be inducers of the bullwhip effect, while others inherently lower demand variability. The main causes of increase in variability are projections of future demand expectations, which result in over-exaggerated responses to changes in demand. We suggest that through appropriate selection and use of certain replenishment rules, the bullwhip effect can be avoided, subsequently allowing supply chain management costs to be lowered.     

A simple heuristic for echelon policies in serial supply chains

This paper proposes a simple heuristic that generates a solution for echelon (r,nQ,T) policies by sequentially solving a deterministic demand problem, a subproblem with fixed reorder intervals, and a subproblem with fixed batch sizes. For each of these problems, we further simplify the computation by solving a series of single-stage systems whose parameters are obtained directly from the original problem data. In a numerical study, we find that this heuristic outperforms an existing one in the literature.     

A simple improvement on Silver's heuristic for the joint replenishment problem

In this paper, we revisit the well-known joint replenishment problem. There is a family of items with a major fixed cost associated with any replenishment of the family and a minor, (item-dependent) setup cost for each item that is included in the replenishment. In contrast with optimization methods and sophisticated (iterative) heuristics that have been presented in the literature, we present a simple (including ease of understanding) improvement routine to be used in conjunction with the original, simple approach advocated by one of the authors 30 years ago. Tests on 48,000 examples reveal that the improvement routine does, indeed, substantially improve performance and with relatively little extra computational effort. Thus, it should be of particular interest to practitioners and for teaching materials.     

A new ILP-based refinement heuristic for Vehicle Routing Problems

In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position, thus leaving an equal number of ``empty holes' in the tour; (b) optimally re-assign the removed nodes to the empty holes through the efficient solution of a min-sum assignment (weighted bipartite matching) problem. We first extend the Sarvanov-Doroshko method to DCVRP, and then generalize it. Our generalization involves a procedure to generate a large number of new sequences through the extracted nodes, as well as a more sophisticated ILP model for the reallocation of some of these sequences. An important feature of our method is that it does not rely on any specialized ILP code, as any general-purpose ILP solver can be used to solve the reallocation model. We report computational results on a large set of capacitated VRP instances from the literature (with symmetric/asymmetric costs and with/without distance constraints), along with an analysis of the performance of the new method and of its features. Interestingly, in 13 cases the new method was able to improve the best-know solution available from the literature. Work supported by M.I.U.R. and by C.N.R., Italy.     

A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

A heuristic method to schedule training programs for Small and Medium Enterprises

During the life period of Small and Medium Enterprises (SMEs) in incubators they need some training programs to acquire the required knowledge in order to survive and succeed in the business environment. This paper presents a heuristic method based on an optimization model to schedule these programs at the most suitable times. Based on the proposed heuristic, each training program is implemented in a suitable time by considering the SMEs’ requirements and some other logical constraints. The proposed heuristic is described in detail, and its implementation is demonstrated via a real-life numerical example. The numerical results of the heuristic are compared with other methods.     

A heuristic algorithm for the hospital health examination scheduling problem

This study considers the problem of health examination scheduling. Depending on their gender, age, and special requirements, health examinees select one of the health examination packages offered by a health examination center. The health examination center must schedule all the examinees, working to minimize examinee/doctor waiting time and respect time and resource constraints, while also taking other limitations, such as the sequence and continuity of the examination procedures, into consideration. The Binary integer programming (BIP) model is one popular way to solve this health examination scheduling problem. However, as the number of examinees and health examination procedures increase, solving BIP models becomes more and more difficult, if not impossible. This study proposes health examination scheduling algorithm (HESA), a heuristic algorithm designed to solve the health examination scheduling problem efficiently and effectively. HESA has two primary objectives: minimizing examinee waiting time and minimizing doctor waiting time. To minimize examinee waiting time, HESA schedules the various parts of each examinee’s checkup for times when the examinee is available, taking the sequence of the examination procedures and the availability of the resources required into account. To minimize doctor waiting time, HESA focuses on doctors instead of examinees, assigning waiting examinees to a doctor as soon as one becomes available. Both complexity analysis and computational analyses have shown that HESA is very efficient in solving the health examination scheduling problem. In addition to the theoretical results, the results of HESA’s application to the concrete health examination scheduling problems of two large hospitals in Taiwan are also reported.     

A column generation approach for location-routing problems with pickup and delivery

In this paper we formulate an integer programming model for the Location and Routing Problem with Pickup and Delivery. We propose a column generation scheme and implement, for the subproblem, a label-setting algorithm for the shortest path with pickup and delivery and time windows problem. We also propose a set of heuristics to speed up this process. To validate the model, we implement the column generation scheme and test it on different instances developed in this paper. We also provide an analysis of how the costs of opening depots and the fixed cost of routes affect the optimal solution.     

An effective and fast heuristic for the Dial-a-Ride problem

Dial-a-Ride is an emerging transport system, in which a fleet of vehicles, without fixed routes and schedules, carries people from the desired pickup point to the desired delivery point, during a pre-specified time interval. It can be modeled as an -hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances (hundred of trips), therefore heuristics are needed. The heuristic method proposed in this paper builds an auxiliary graph and then solves an assignment problem on this graph. The auxiliary graph is obtained by replacing pairs of nodes with a single one and associating an ad hoc cost function to the new set of arcs. Two different simple methods are employed to transform the infeasible solution given by the assignment problem into a feasible one. The proposed algorithms have been tested on instances created using the Milan network and shown to be fast and effective.      

A simulated annealing heuristic for the team orienteering problem with time windows

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.     

Improving fleet utilization for carriers by interval scheduling

Carriers are under increasing pressure to offset rising fuel charges with cost cutting or revenue generating schemes. One opportunity for cost reduction lies in asset management. This paper presents resource allocation scheduling models that can be used to assign truck loads to delivery times and trucks when delivery times are flexible. The paper makes two main contributions. First, we formulate the problem as a multi-objective optimization model — minimizing the number of trucks needed as well as the costs associated with tardiness or earliness — and demonstrate how improvements in fleet usage translate into savings which carriers can use as incentives to promote flexible delivery times for customers. Second, we show that a two-phase model with a polynomial algorithm in the second phase is able to produce optimal schedules in a reasonable time.     

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 multi-commodity, capacitated pickup and delivery problem: The single and two-vehicle cases

We explore dynamic programming solutions for a multi-commodity, capacitated pickup and delivery problem. Cargo flows are given by an origin/destination matrix which is not necessarily symmetric. This problem is a generalization of several known pickup and delivery problems, as regards both problem structure and objective function. Solution approaches are developed for the single-vehicle and two-vehicle cases. The fact that for each cargo that goes from a node i to another node j there may be a cargo going in the opposite direction provides the motivation for the two-vehicle case, because one may conceivably consider solutions where no cargoes that travel in opposite directions between node pairs are carried by the same vehicle. Yet, it is shown that such scenarios are generally sub-optimal. As expected, the computational effort of the single vehicle algorithm is exponential in the number of cargoes. For the two-vehicle case, said effort is of an order of magnitude that is not higher than that of the single-vehicle case. Some rudimentary examples are presented or both the single-vehicle and two-vehicle cases so as to better illustrate the method.     

A heuristic procedure for solving the dynamic probabilistic project expediting problem

Because of activity duration uncertainties, large-scale projects can often be modeled most realistically as probabilistic activity networks. The complex interactions among activities with uncertain durations virtually assures a low probability that these projects will be completed before predetermined due dates. As a result, it is often necessary to expedite individual activities in these projects to improve due date performance. This research introduces a dynamically applied matrix simulation approach for selecting expediting options in order to control the probability of successful project completion before predefined due dates. Experiments are conducted to demonstrate the ability of this new approach to generate quality alternatives and efficiently evaluate large-scale projects.     

A framework for the value of information in inventory replenishment

Technological advances and changes in supply chain management practices have combined to draw attention to the value of information sharing in inventory replenishment. Academic research has produced seemingly conflicting results due to differences in the type of information that is shared, the supply chain structure, and the selection and parameterization of performance goals. This research provides a framework to help explain apparent differences in the extant literature. Our purpose is to understand what determines the value of information. With this specific view, we establish a set of research questions and suggest directions for future research.