Optimal routing and process scheduling for a mobile service facility

Abstract

Abstract This paper deals with the problem of delivering a well‐defined service to a given set of points efficiently. Efficiencies are sought through providing the services by use of a mobile service unit (MSU). The service facility is mobile in the sense that it can move from point to point at some “move” cost. Unlike the traveling salesman‐type problems however the present problem does not require a physical visit to every point for servicing. Points can be serviced from a distance, while the facility is stationed at a nearby point, at some “processing” cost that may depend on many factors, including the distance involved. The problem is to find the subset and the sequence of nodes that the mobile service unit should physically visit and the set of other points it should service while at each of these visited nodes so as to minimize the sum of move and processing costs. A Lagrangean‐based branch‐and‐bound algorithm is proposed. This algorithm is aided by a powerful upper‐boundig routine and sensitivity tests and logical dominance rules to fix zero/one variables. Somewhat encouraging computational results are presented.