| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Local authorities and public services Description
Further explanation of this example: 'Applications of optimization with Xpress-MP', Chapter 15: Local authorities and public services
Source Files By clicking on a file name, a preview is opened at the bottom of this page. Data Files
j4grit.mos (!****************************************************** Mosel Example Problems ====================== file j4grit.mos ``````````````` Gritting roads in a village A directed graph representing street intersections (nodes) and streets required to be gritted (arcs) is provided. Street lengths are arc attributes, and the initial location of a gritting truck is also known. Determine a tour for the gritting truck of minimum total length that passes through all streets. The graph is implemented as an adjacency matrix. Decision variables represent the frequency of use of an arc (streets). Since a Eulerian circuit is asked, the function 'addpath' is implemented to obtain the Eulerian circuit post optimization from the decision variables solution. (c) 2008-2022 Fair Isaac Corporation author: S. Heipcke, Mar. 2002, rev. Mar. 2022 *******************************************************!) model "J-4 Gritting circuit" uses "mmxprs" forward function findunused(J: array(range) of integer):integer forward function addpath(node:integer, J: array(range) of integer):integer declarations ISEC = 1..12 ! Set of street intersections LEN: dynamic array(ISEC,ISEC) of integer ! Length of streets use: dynamic array(ISEC,ISEC) of mpvar ! Frequency of use of streets end-declarations initializations from 'j4grit.dat' LEN end-initializations forall(i,j in ISEC | exists(LEN(i,j))) create(use(i,j)) ! Objective: length of circuit Length:= sum(i,j in ISEC | exists(LEN(i,j))) LEN(i,j)*use(i,j) ! Balance traffic flow through intersections forall(i in ISEC) sum(j in ISEC) use(i,j) = sum(j in ISEC) use(j,i) ! Grit every street forall(i,j in ISEC | exists(LEN(i,j))) use(i,j) >= 1 ! Solve the problem minimize(Length) ! Solution printing writeln("Total length: ", getobjval) ct:=round(getsol(sum(i,j in ISEC) use(i,j))) declarations TOUR: array(1..ct+1) of integer TCOUNT: array(ISEC,ISEC) of integer end-declarations ! Main loop of the Eulerian circuit algorithm forall(i,j in ISEC | exists(LEN(i,j))) TCOUNT(i,j):=round(getsol(use(i,j))) TOUR(1):=1 ct-=addpath(1,TOUR) while(ct>0) ct-=addpath(findunused(TOUR),TOUR) writeln("Tour: ", TOUR) !----------------------------------------------------------------- ! Find first node in list with free path(s) function findunused(J: array(range) of integer):integer i:=1 returned:=1 while(J(i)>0 and i<getsize(J)) if (sum(j in ISEC) TCOUNT(J(i),j) > 0) then returned:=J(i) break else i+=1 end-if end-function !----------------------------------------------------------------- ! Add a subtour to the current tour function addpath(node:integer, J: array(range) of integer):integer declarations NEWJ: array(1..getsize(J)) of integer end-declarations ! Insertion position pos:=1 while(J(pos)<>node and pos<getsize(J)) pos+=1 ! Find a new path cur:=node; newct:=0 while(sum(j in ISEC) TCOUNT(cur,j) > 0) do forall(j in ISEC) if(TCOUNT(cur,j) > 0) then TCOUNT(cur,j)-=1 newct+=1; NEWJ(newct):=j cur:=j break end-if end-do ! Add the new path to main journey i:=getsize(J)-newct while(i>pos) do J(i+newct):=J(i) i-=1 end-do forall(j in 1..newct) J(pos+j):=NEWJ(j) returned:=newct end-function end-model | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
© Copyright 2023 Fair Isaac Corporation. |