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.     

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits

We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.     

An optimization approach for communal home meal delivery service: A case study

This paper is the first to discuss the communal home meal delivery problem. The problem can be modelled as a multiple travelling salesman problem with time windows, that is closely related to the well-studied vehicle routing problem with time windows. Experimental results are reported for a real-life case study from Central Finland over several alternative scenarios using the SPIDER commercial solver. The comparison with current practice reveals that a significant savings potential can be obtained using off-the-shelf optimization tools. As such, the potential for supporting real-life communal routing problems can be considered to be important for VRP practitioners.     

An exact algorithm for a single-vehicle routing problem with time windows and multiple routes

This paper describes an exact algorithm for solving a problem where the same vehicle performs several routes to serve a set of customers with time windows. The motivation comes from the home delivery of perishable goods, where vehicle routes are short and must be combined to form a working day. A method based on an elementary shortest path algorithm with resource constraints is proposed to solve this problem. The method is divided into two phases: in the first phase, all non-dominated feasible routes are generated; in the second phase, some routes are selected and sequenced to form the vehicle workday. Computational results are reported on Euclidean problems derived from benchmark instances of the classical vehicle routing problem with time windows.     

Runway sequencing with holding patterns

We study a scheduling problem, motivated by air-traffic control. When aircraft reach the final descent in the “Terminal Radar Approach CONontrol” area (tracon), a set of disjoint time windows in which the landing is possible, can be automatically assigned to each aircraft. The objective is then to determine landing times, within these time windows, which maximize the minimum time elapsed between consecutive landings. We study the complexity of the problem and describe several special cases that can be solved in polynomial time. We also provide a compact Mixed Integer Programming formulation that allows us to solve large instances of the general problem when all time windows have the same size. Finally, we introduce a general hybrid branch and cut framework to solve the problem with arbitrary time windows. Experimental results show that our approach outperforms earlier formulation of the problem.     

Heuristics to Schedule Service Engineers within Time Windows

This paper describes the development of a set of heuristics for tackling vehicle routeing problems with time windows (VRPTW) subject to uncertain demand where schedules are prepared interactively. Many public utility companies, e.g. gas, water, electricity, are now having to quote very specific times for visits to customers, both for regular service and emergency call-outs. The heuristics developed produce good tours by sequencing visits on the basis of closeness to existing visits. Tours are developed as and when demand occurs so that the customer is given an immediate appointment time, rather than waiting for a number of requests for service to be received. Simple methods to construct time windows will also be discussed.     

Matheuristics for solving a multi-attribute collection problem for a charity organisation

This paper studies a real-life multi-attribute profit collecting vehicle routing problem, arising in the collection operations of a charity organisation in the United Kingdom. The problem involves a heterogeneous fleet of vehicles of different capacities, mandatory visits to a subset of vertices, time windows, rest requirements associated with maximum driving and working times, and partial collection. A mixed integer programming formulation of the problem is described, along with three matheuristics based on Tabu Search and Large Neighbourhood Search. Computational results on instances derived from the case study are presented, and insights are given from a practical implementation.     

The rural postman problem with deadline classes

Vehicle routing problems with general time windows are extremely difficult to solve. However, the time windows in a particular problem may have a special structure which can be exploited. We consider a single-vehicle arc-routing problem in which the arcs are partitioned into deadline classes. It is shown that a cutting-plane approach works well for this problem.     

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.     

A framework for optimization under ambiguity

Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called Adaptive Tabu Search and Adaptive Genetic Algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.     

Characterizing the Shapley value in fixed-route traveling salesman problems with appointments

Starting from her home, a service provider visits several customers, following a predetermined route, and returns home after all customers are visited. The problem is to find a fair allocation of the total cost of this tour among the customers served. A transferable-utility cooperative game can be associated with this cost allocation problem. We introduce a new class of games, which we refer as the fixed-route traveling salesman games with appointments. We characterize the Shapley value in this class using a property which requires that sponsors do not benefit from mergers, or splitting into a set of sponsors.     

Combined vehicle routing and scheduling with temporal precedence and synchronization constraints

We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where in the literature the temporal constraints are usually remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usefulness. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct use of a commercial solver against the proposed heuristic, where the latter approach can find high quality solutions within specific time limits.     

Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem. It deals with route planning and the distribution of goods from a depot to geographically dispersed customers by a fleet of vehicles with constrained capacities. The customers’ demands are known and each customer has a time window in which it has to be supplied. The time windows are assumed to be soft, that means, violations of the time windows are allowed, but associated with penalties. The problem is to organize the vehicle routes optimally, i.e. to minimize the total costs, consisting of the number of used vehicles and the total distance, and the penalties simultaneously. Thus, the problem is formulated as a bicriterion minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs.     

Combined Routeing and Scheduling for the Transportation of Containerized Cargo

A tractor-trailer problem, with full load, from the class of combined routeing and scheduling problems is described. Distinctive features of the problem are: movements must be carried out within certain time windows; subsets of movements are linked in the sense that they must be executed in a certain order; and different priorities are attached to different movements. A new bidirectional sequential constructive heuristic is developed for the solution of this problem. The method constructs routes and schedules for the available tractor fleet. The algorithm attempts to minimize the total time for all the movements by minimizing the time taken up by unproductive movements (so-called deadhead) and waiting time between movements. Some practical aspects of the implementation of the approach are discussed.     

Solving routing problems with pairwise synchronization constraints

Pairwise route synchronization constraints are commonly encountered in the field of service technician routing and scheduling and in the area of mobile care. Pairwise route synchronization refers to constraints that require that two technicians or home care workers visit the same location at exactly the same time. We consider constraints of this type in the context of the well-known vehicle routing problem with time windows and a generic service technician routing and scheduling problem. Different approaches for dealing with the problem of pairwise route synchronization are compared and several ways of integrating a synchronization component into a metaheuristic algorithm tailored to the original problems are analyzed. When applied to benchmark instances from the literature, our algorithm matches almost all available optimal values and it produces several new best results for the remaining instances.

     

Single machine scheduling problem with multiple due windows assignment in a group technology

We consider group scheduling problem on a single machine with multiple due windows assignment. Jobs are divided into groups in advance according to their processing similarities, and all jobs of the same group are required to be processed contiguously on the machine in order to achieve production efficiency and save time/money resource. A sequence-independent setup time precedes the processing of each group. The goal is to determine the optimal sequence for both groups and jobs, together with an optimal combination of the due windows assignment strategy so as to minimize the total of earliness, tardiness and due windows related costs. We give an \(O(n\log n)\) time algorithm for the problem.     

Scheduling healthcare services in a home healthcare system

We consider a scheduling problem in a home healthcare system in which nurses visit patients regularly for relatively minor healthcare services. Intervals between the visits may differ for different patients. On each day in the planning horizon, a nurse must visit the patients assigned to her/him on that day, and then return to the hospital. For the problem of determining the visiting schedule with the objective of minimizing total travel time of the nurse over the planning horizon, we develop a two-phase heuristic algorithm. To evaluate performance of the proposed algorithm, a series of computational tests is performed on a number of randomly generated problem instances and a real instance. Results of the tests show that the heuristic algorithm gives near optimal solutions for problems of practical sizes in a reasonable 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.     

Lot-sizing with production and delivery time windows

We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs. For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Effective Heuristic Procedures for a Field Technician Scheduling Problem

This paper addresses a field technician scheduling problem faced by many service providers in telecommunication industry. The problem is to assign a set of jobs, at different locations with time windows, to a group of field technicians with different job skills. Such a problem can be viewed as a generalization of the well-known vehicle routing problem with time windows since technician skills need to be matched with job types. We designed and tested several heuristic procedures for solving the problem, namely a greedy heuristic, a local search algorithm, and a greedy randomized adaptive search procedure (GRASP). Our computational results indicate that GRASP is the most effective among them but requires more CPU time. However, the unique structure of GRASP allows us to exploit parallelism to achieve linear speed-up with respect to the number of machines used.