# Gritting Roads

## Contents

## Problem description

In the case of ice, all the streets of a village need to be gritted. A schematic map of the streets is given in the figure below. The nodes correspond to street intersections, the arcs to the streets that need to be gritted. The arcs are labeled with the length of the street in meters.

Graph of the village streets

--150-> --130-> --100-> 1 2 3 4 <-140-- <-100-- | ^ /| ^ ^ | ^ | 165 / | 170 | | 180 | | / | | 200 | | 165| 230 160| | 190| | | / | | | | | | | / | | | | | V |V V | | V | --144-> --128-> 5 6 7 --109-> 8 <-144-- <-122-- ^ /| ^ ^| ^ / | 194 / |174 / | | / | | / | | / 185|185 / | | 218 174| 233 | | / 190 | / | | / | | 140 | | / | | / | | / | | V V |/ V |V V

9 --148-> 10 <-135- 11 -110-> 12

The highway maintenance depot with the gritting truck is located at intersection number 1. The truck has a sufficiently large capacity to grit all the streets during a single tour. Due to the one-way streets, it may be forced to pass several times through the same street that has already been gritted. Determine a tour for the gritting truck of minimum total length that passes through all streets. For bidirectional streets, both directions need to be gritted separately.

## Variables

in/out Road i starts in in(i) and goes out to out(i) lengths Lengths of the roads

## Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com % Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$ % Written Oct 7, 2005. Last modified Apr 8, 2009.

## Problem setup

in = [1 1 2 2 2 3 3 4 4 5 5 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10 10 11 11 12]'; out = [2 5 3 5 6 2 4 3 8 1 6 2 5 7 9 10 3 6 8 11 4 11 12 5 10 6 7 7 10 11]'; lengths = [150 165 130 230 160 140 100 100 190 165 144 170 144 128 218 174 ... 200 122 109 185 180 141 190 194 148 174 233 185 135 110]'; n = length(lengths); %Number of arcs arcs = tom('arcs',n,1,'int'); % All variables are integer bnds = {1 <= arcs}; % Districts chosen n1 = length(unique([in;out])); con = cell(n1,1); for i=1:n1 idxin = find(i == in); idxout = find(i == out); con{i} = {sum(arcs(idxin)) == sum(arcs(idxout))}; end % Objective objective = lengths'*arcs; constraints = {bnds, con}; options = struct; options.solver = 'cplex'; options.name = 'Gritting Roads'; sol = ezsolve(objective,constraints,[],options); PriLev = 1; if PriLev > 0 twice = find(sol.arcs > 1); disp('all roads travelled once, except:') for i = 1:length(twice), idx = twice(i); disp([' road from ' num2str(in(idx)) ' to ' num2str(out(idx)) ... ' ( that is travelled ' num2str(sol.arcs(idx)) ' times)']) end end % MODIFICATION LOG % % 051206 med Created % 060118 per Added documentation % 060125 per Moved disp to end % 090325 med Converted to tomSym

Problem type appears to be: mip ===== * * * =================================================================== * * * TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05 ===================================================================================== Problem: --- 1: Gritting Roads f_k 5990.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 7 Elapsed time: 0.016000 sec. all roads travelled once, except: road from 3 to 4 ( that is travelled 2 times) road from 4 to 8 ( that is travelled 2 times) road from 5 to 1 ( that is travelled 2 times) road from 5 to 6 ( that is travelled 2 times) road from 6 to 9 ( that is travelled 2 times) road from 10 to 6 ( that is travelled 2 times) road from 11 to 7 ( that is travelled 2 times)