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.     

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.     

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.

     

Iterated local search for workforce scheduling and routing problems

The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times.     

Exact and hybrid methods for the multiperiod field service routing problem

This article deals with a particular class of routing problem, consisting of the planning and routing of technicians in the field. This problem has been identified as a multiperiod, multidepot uncapacitated vehicle routing problem with specific constraints that we call the multiperiod field service routing problem (MPFSRP). We propose a set covering formulation of the problem for the column generation technique and we develop an exact branch and price solution method for small-sized instances. We also propose several heuristic versions for larger instances. We present the results of experiments on realistic data adapted from an industrial application.     

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 Manpower Allocation Model of Job Specialization

A major copier machine company in Hong Kong presently faces the problem of providing effective servicing and repairing support to its four service regions. Due to the shortage of skilled technicians and the variety of jobs to be handled by technicians of differing skill levels, its Service Department appears to be understaffed, experiencing substantial daily backlogs. This study concentrates on a new perspective of operation: the assignment of technicians at each skill level to specialize in a single type of job in one of the four regions. The objective is to maximize the overall daily number of completed service calls. A mathematical model is developed to handle this specialized allocation problem, where the average travel time (forming part of the coefficient of one of the model's variables) of a technician servicing a type of job in a region is dependent on the decision variables – the composition of the whole team. This results in what we call a mixed integer non-linear programme with variable coefficients. An exact solution is obtained by an iterative algorithm with an overall dynamic programming approach. Sample numerical results are also reported.     

A simulation-based approach for fleet design in a technician dispatch problem with stochastic demand

We address the problem of developing policies for selecting the proper number of technicians to hire (fleet size) for an on-call repair service operating over a yearly planning horizon in an environment where the number of requests to be serviced each day can vary significantly from day to day and on a seasonal basis. We propose a new approach based on the simulation of a large number of sampled weekly instances and the application of a previously developed optimization procedure for the daily dispatch of technicians. The sampled instances are derived from an extensive statistical analysis of demand data with respect to several key parameters. The results of the simulations are utilized to adjust performance curves in function of fleet size that are then used in an economic analysis of the trade-offs between service quality and cost. Efficient policies for fleet design are then deducted from this analysis.     

Optimising a general repair kit problem with a service constraint

Field services are a particular type of after-sales service performed at the customer’s location where technicians repair malfunctioning machines. The inventory decisions about which spare part types to take to the repair site and in what quantities is called the repair kit problem. This problem is characterized by an order-based performance measure since a customer is only satisfied when all required spare parts are available to fix the machine. As a result, the service level in the decision making process is defined as a job fill rate. In this paper we derive a closed-form expression for the expected service level and total costs for the repair kit problem in a general setting, where multiple units of each part type can be used in a multi-period problem. Such an all-or-nothing strategy is a new characteristic to investigate, but commonly used in practice. Namely, items are only taken from the inventory when all items to perform the repair are available in the right quantity. We develop a new algorithm to determine the contents of the repair kit both for a service and cost model while incorporating this new expression for the job fill rate. We show that the algorithm finds solutions which differ on average 0.2% from optimal costs. We perform a case study to test the performance of the algorithm in practice. Our approach results in service level improvements of more than 30% against similar holding costs.     

Sensitivity analysis of machine repair problems in manufacturing systems with service interruptions

This paper models a manufacturing system consisting of M operating machines and S spare machines under the supervision of a group of technicians in a repair facility. Machines fail according to a Poisson process, and the repair (service) process of a failed machine may require more than one phase. In each phase, service times are assumed to be exponentially distributed but may be interrupted when the repair facility encounters unpredictable breakdowns. Two models of manufacturing systems are considered. In the first model, technicians repair failed machines at different rates in each phase. In the second model, a two-phase service system with differing numbers of technicians is considered. Profit functions are developed for both models and optimized by a suitable allocation of the number of machines, spares, and technicians in the system. Finally, a sensitivity analysis (see Cao [X.R. Cao, Realization Probabilities: The Dynamics of Queuing Systems, Springer-Verlag: London, 1994; X.R. Cao, The relations among potentials, perturbation analysis, and Markov decision processes, Discrete Event Dynam. Syst.: Theory Applicat. 8 (1998) 71–87]) is performed to provide an approach that quantifies the impact of changes in the parameters on the profit models.     

An emergency vehicle dispatching system for an electric utility in Chile

Chilean companies have only recently begun developing and implementing computerised systems to aid in decision making, related to the assignment and routing of vehicles. This paper presents the problem of assigning and routing repair vehicles for the Emergency Services Division of Chilectra S.A., the electricity utility for the city of Santiago, the capital of Chile. A computerised system based on heuristic algorithms was developed for vehicle routing with random demand which represent breakdowns that require a repair crew. An exponential smoothing method was implemented for the prognosis of breakdowns. Evaluation of the system's performance showed a 16% improvement in service quality as measured by the time required for servicing breakdowns under regular conditions and a 53% improvement under adverse climate conditions.     

An exact static solution approach for the service parts end-of-life inventory problem

This paper studies the spare parts end-of-life inventory problem that happens after the discontinuation of part production. A final ordering quantity is set such that the service process is sustained until all service obligations expire. Also, the price erosion of substitutable or new generation products over time makes it economically justifiable to consider switching to an alternative service policy for repair such as swapping the old product with a new one. This requires the joint optimization of the final order quantity and the time to switch from repair to an alternative service policy. To the best of our knowledge, the problem has not been optimally solved yet either in its static or dynamic formulation. In the current paper, we solve its static version as a bi-level optimization problem. We investigate the convexity of the objective function and give a computationally efficient algorithm to find an exact optimal solution up to any given numerical error level ??>?0. We illustrate our approach on some numerical examples and compare our results with earlier works on this problem.     

Dynamic multi-priority,multi-class patient scheduling with stochastic service times

Efficient patient scheduling has significant operational, clinical and economical benefits on health care systems by not only increasing the timely access of patients to care but also reducing costs. However, patient scheduling is complex due to, among other aspects, the existence of multiple priority levels, the presence of multiple service requirements, and its stochastic nature. Patient appointment (allocation) scheduling refers to the assignment of specific appointment start times to a set of patients scheduled for a particular day while advance patient scheduling refers to the assignment of future appointment days to patients. These two problems have generally been addressed separately despite each being highly dependent on the form of the other. This paper develops a framework that incorporates stochastic service times into the advance scheduling problem as a first step towards bridging these two problems. In this way, we not only take into account the waiting time until the day of service but also the idle time/overtime of medical resources on the day of service. We first extend the current literature by providing theoretical and numerical results for the case with multi-class, multi-priority patients and deterministic service times. We then adapt the model to incorporate stochastic service times and perform a comprehensive numerical analysis on a number of scenarios, including a practical application. Results suggest that the advance scheduling policies based on deterministic service times cannot be easily improved upon by incorporating stochastic service times, a finding that has important implications for practice and future research on the combined problem.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

New developments in the primal–dual column generation technique

The optimal solutions of the restricted master problems typically leads to an unstable behavior of the standard column generation technique and, consequently, originates an unnecessarily large number of iterations of the method. To overcome this drawback, variations of the standard approach use interior points of the dual feasible set instead of optimal solutions. In this paper, we focus on a variation known as the primal–dual column generation technique which uses a primal–dual interior point method to obtain well-centered non-optimal solutions of the restricted master problems. We show that the method converges to an optimal solution of the master problem even though non-optimal solutions are used in the course of the procedure. Also, computational experiments are presented using linear-relaxed reformulations of three classical integer programming problems: the cutting stock problem, the vehicle routing problem with time windows, and the capacitated lot sizing problem with setup times. The numerical results indicate that the appropriate use of a primal–dual interior point method within the column generation technique contributes to a reduction of the number of iterations as well as the running times, on average. Furthermore, the results show that the larger the instance, the better the relative performance of the primal–dual column generation technique.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

Freight railway operator timetabling and engine scheduling

In this paper we consider timetable design at a European freight railway operator. The timetable is designed by choosing the time of service for customer unit train demands among a set of discrete points. These discrete points are all found within the a time-window. The objective of the model is to minimize cost while adhering to constraints regarding infrastructure usage, demand coverage, and engine availability. The model is solved by a column generation scheme where feasible engine schedules are designed in a label setting algorithm with time-dependent cost and service times.     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints

We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.     

The Prospect Award 1981: A Manpower Planning Model for Mobile Repairmen

The country's largest vending machine operators and distributors were faced with the problem of evaluating manpower requirements and structure for the repair and maintenance work force, and of deciding where additions to this force should be located. This paper describes the formulation and application of a solution to the problem which has had beneficial effects far beyond the scope originally envisaged.The work force concerned operates a breakdown repair service which requires random journeys within each individual's prescribed area. The developed model evaluates the work content, and thus manpower requirements, of a region based on the number of machines, the breakdown rates, the repair times and the journey time. The travel component is automatically adjusted for growth in the work force.Analysis of the model's sensitivity to the key factors and the development of the relationship between utilisation and service level have enabled the company to improve service performance by 15% while also achieving a 67% increase in productivity.