Optimisation with MiniZinc - Vehicle Routing Problem --------------------- This MiniZinc modelling exercise can be done in groups. This vehicle routing problem has several variants, all of which can be modelled using MiniZinc. The first variant (Problem 1) will be used to solve the basic problem. This variant will then be modified and extended to handle the additional vehicle routing constraints. Three example data sets for testing the MiniZinc models are supplied. Requirements for MiniZinc model ------------------------------- The ideal solution should run on all three problem instances given below, just by changing the data. ------------------------------------------------------------ Problem Specification - Problem 1 ----------------------------------------------- There are two warehouses, A and B. Each warehouse has a fixed set of customers. No customer is served by both warehouses - so the two sets are disjoint. Each warehouse has a truck, serving only its own customers. There is a table of distances from customer to warehouse and between the customers. It is assumed that the trucks travel at a constant speed, so we can assume the table of distances is also a table of times. Assuming both trucks leave their warehouses at time 0, minimise the time at which the later truck returns to its warehouse. There are three instances of the problem. In the smallest instance each warehouse has 3 customers. This is called the "size 3" problem instance. There is a size 4 problem instance, where each warehouse has 4 customers, and a size 5 problem instance, where each warehouse has 5 customers. Since we are not concerned about runtime performance, it may be that your model fails to terminate on the larger instances for model 2. However it should at least find an optimal solution for the size 3 problem instance for model 1. Constraints - Model 1 --------------------- These constraints must always be satisfied by any solution. The truck associated with warehouse A starts at the location of the warehouse A, and also finishes back at the warehouse. Similarly the other truck starts and finishes at warehouse B. Each truck visits all the customers of its warehouse. Additional Information - Model 1 -------------------------------- The distances satisfy the "triangle inequality", which means it is shorter to travel direct between any two locations than to travel via a third location. The consequence of this assumption is that the shortest trip will leave the warehouse, visit each customer of the warehouse exactly once, and then return to the warehouse. A second consequence is that the number of locations visited on the shortest trip can be specified as a parameter. ------------------------------------------------------------------- Time Windows - Problem 2 -------------------------------- This is the same as problem 1: each truck visits all the customers of its warehouse. The difference is that each customer has an associated "time window". A time window is an earliest and latest arrival time: the truck visiting the customer must arrive between these two times. (The truck may arrive at the earliest or latest time, or between the two times.) The requirement is the same - to minimise the time at which the later truck returns to its warehouse. ------------------------------------------------------------------- Shared Customer Problem, with balanced work - Problem 3 ------------------------------------------------------- This problem uses the same data as Problem 1, but in this problem a truck is allowed to deliver not only to customers of its own warehouse, but also to customers of the other warehouse. Every customer must be visited by at least one truck. Each truck must start and finish at its own warehouse. To keep the model simple we add an additional constraint that the number of customers visited by each truck is the same. The objective is the same: to minimise the time at which the last truck returns to its warehouse. -------------------------------------------------------------------- Data for the three problem instances. ------------------------------------- If N is the size of the problem instance, the data is available in a file named: sizeN.dzn A stands for warehouse A A1,A2,.. AN are its customers B stands for warehouse B B1, B2, BN are its customers. The parameters supplied by the data are: int: Size array [1..LocSize, 1..LocSize] of int: Dist array [1..LocSize,1..2] of int: TimeWindow % where LocSize = 2*(Size+1) The "Dist" table records the distance between each pair of locations. Notice that the distance from location X to Y is always the same as the distance from Y to X. The distance from X to X is, of course, 0. The distances satisfy the triangle inequality, so it is always as fast or faster to go direct from X to Y than to go from X to Y via some other location Z. The "TimeWindows" table associates a time window with each location. The time windows associated with the warehouses can be ignored. Trucks always leave the warehouse at time 0. (In fact the size 5 data can be used for all three instances. The smaller instances simply use part of the largest table.) %%%%% Parameters for size 3 instance %%%%%%%% Size = 3 ; Dist = % A A1 A2 A3 B B1 B2 B3 [| 0, 160, 150, 590, 340, 650, 725, 560 % A |160, 0, 260, 680, 280, 650, 820, 715 % A1 |150, 260, 0, 440, 260, 520, 620, 490 % A2 |590, 680, 440, 0, 490, 240, 390, 435 % A3 |340, 280, 260, 490, 0, 660, 800, 700 % B |650, 650, 520, 240, 660, 0, 160, 250 % B1 |725, 820, 620, 390, 800, 160, 0, 210 % B2 |560, 715, 490, 435, 700, 250, 210, 0|] ; % B3 TimeWindow = [|0,1000 |800,1500 %A1 |100,600 %A2 |200,1500 %A3 |0, 500 |0, 1500 %B1 |200,1700 %B2 |100,1200 %B3 |] ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Parameters for size 4 instance %%%%%%%%%%%%%%%%%%%%% Size = 4 ; Dist = % A A1 A2 A3 A4 B B1 B2 B3 B4 [| 0, 160, 150, 590, 340, 650, 725, 560, 350, 200 % A |160, 0, 260, 680, 280, 650, 820, 715, 500, 150 % A1 |150, 260, 0, 440, 260, 520, 620, 490, 280, 150 % A2 |590, 680, 440, 0, 490, 240, 390, 435, 400, 550 % A3 |340, 280, 260, 490, 0, 660, 800, 700, 510, 140 % A4 |650, 650, 520, 240, 660, 0, 160, 250, 340, 670 % B |725, 820, 620, 390, 800, 160, 0, 210, 380, 780 % B1 |560, 715, 490, 435, 700, 250, 210, 0, 215, 650 % B2 |350, 500, 280, 400, 510, 340, 380, 215, 0, 450 % B3 |200, 150, 150, 550, 140, 670, 780, 650, 450, 0 |] ; % B4 TimeWindow = [|0, 1000 |800,1500 %A1 |100, 600 %A2 |200,1500 %A3 |0, 500 %A4 |0, 1500 |200,1700 %B1 |100,1200 %B2 |600,2500 %B3 |300,1700 %B4 |] ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% Parameters for the size 5 instance %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Size = 5 ; Dist = % A A1 A2 A3 A4 A5 B B1 B2 B3 B4 B5 [| 0, 160, 150, 590, 340, 650, 725, 560, 350, 200, 460, 160 |160, 0, 260, 680, 280, 650, 820, 715, 500, 150, 500, 120 |150, 260, 0, 440, 260, 520, 620, 490, 280, 150, 330, 300 |590, 680, 440, 0, 490, 240, 390, 435, 400, 550, 210, 750 |340, 280, 260, 490, 0, 660, 800, 700, 510, 140, 280, 395 |650, 650, 520, 240, 660, 0, 160, 250, 340, 670, 420, 810 |725, 820, 620, 390, 800, 160, 0, 210, 380, 780, 570, 900 |560, 715, 490, 435, 700, 250, 210, 0, 215, 650, 550, 715 |350, 500, 280, 400, 510, 340, 380, 215, 0, 450, 420, 510 |200, 150, 150, 550, 140, 670, 780, 650, 450, 0, 460, 250 |460, 500, 330, 210, 280, 420, 570, 550, 420, 460, 0, 590 |160, 120, 300, 750, 395, 810, 900, 715, 510, 250, 590, 0 |] ; TimeWindow = [|0, 1000 |800,1500 %A1 |100, 600 %A2 |200,1500 %A3 |0, 500 %A4 |0, 1500 %A5 |200,1700 |100,1200 %B1 |600,2500 %B2 |300,1700 %B3 |500,1800 %B4 |0, 2500 %B5 |]; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%