Discrete Operations Research · 2023 - 2024
Discrete Operations Research
Assignment
(20% of course grade)
Due Date: 19 December 2023, 23:59
1. The assignment is to be completed by the assignment team you created in Brightspace. No changes
to the teams are allowed at this point.
2. Hand in your answers before the deadline via Brightspace (one submission per team). You do not need to turn in a paper copy.
3. Turn in separate files per question, as follows. For question 1 turn in a PDF file containing only the your answer to question 1. For question 2 turn in a PDF file containing only the answer to question 2. For Question 3, you need to turn in three files (two .py files and one .csv file) as explained in detail at the end of question 3.
4. For question 1 and question 2, put your group number in the name of the file, so that the name of the file becomes “Assignment1_Group[group number]_Question[question number].pdf”.
5. Do not use any compression software (such as ZIP, RAR or ARJ). So upload the five files individually in Brightspace.
6. For each PDF you submit, put your names and student numbers and your group number at the top of the first page.
7. Use LaTeX to write your solutions, handwritten solutions are not allowed.
8. This assignment will be graded out of 100, and will constitute 20% of your overall course grade.
Question 1 (25 points)
An infeasible solution to the Traveling Salesman Problem (TSP) on a complete graph with node set
N = {1,2,3,4,5,6,7} is given below.
Recall three ways of formulating subtour elimination constraints (SECs) in the Traveling Salesman Problem
(TSP):
XX
(Option1) (Option2) (Option3)
xij ≤|S|−1, XX
xij ≥1,
forallS⊂N, S̸=∅ forallS⊂N, S̸=∅
i∈S j∈S
i∈S j∈N\S
ui−uj +nxij ≤n−1 ∀i,j=2,...,n
Discrete Operations Research · 2023 - 2024
(a) State all SECs of option 1 that are violated by the given infeasible solution. Write down the
P
constraints explicitly, without using the summation ( each SEC the corresponding node subset S.
) or for all ( ∀ ) notation. Clearly state for (b) State all SECs of option 2 that are violated by the given infeasible solution. Write down the
constraints explicitly, without using the summation ( each SEC the corresponding node subset S.
) or for all ( ∀ ) notation. Clearly state for (c) Prove that the depicted solution is not feasible according to the SECs of option 3.
Question 2 (25 points)
(a) Let a directed graph G = (N,A) be given, where N = {0}∪C is the set of nodes, where 0 denotes the depot and C denotes the set of customers, and A is the set of arcs. The set of customer nodes C = C R ∪ C O contains a set of required customers C R , which are customers that must be visited, and a set of optional customers CO, which are customers that can be visited but are not required to be visited. If an optional customer i ∈ CO is not visited, a penalty cost pi is incurred. A travel cost cij is associated to each arc (i,j) ∈ A. For each node i ∈ C a demand qi is given. A fleet of K vehicles, each with capacity Q, is located at the depot.
The problem is to find a set of routes starting and ending at the depot, visiting the required customers and possibly some or all optional customers, such that the capacity of the vehicles is not violated. The objective of the problem is to minimize the sum of the total travel cost and the total penalties for not visiting optional customers.
Formulate this problem as an integer linear programming model by adapting the 2-index linear programming formulation for the capacitated VRP (asymmetric), as given in the lecture slides (Slide 8 of Lecture 3, LaTeX source given below). Use binary variable yi to indicate whether customer i is visited or not. Provide the complete formulation.
Hint: you should only make changes to the objective, Constraints (2) and/or Constraints (3) (as numbered on slide 8 of lecture 3), and/or add additional constraint(s). All other constraints remain unaltered.
LaTeX source for the capacitated VRP:
\begin{align}
\min \quad & \sum_{(i, j) \in A} c_{ij} x_{ij} && \\
s. t. \quad & \sum_{j \in \delta^+(i)} x_{ij} = 1 && \forall i \in C \\ & \sum_{j \in \delta^-(i)} x_{ji} = 1 && \forall i \in C \\
& \sum_{i \in \delta^+(0)} x_{0i} = K && \\
& \sum_{i \in \delta^-(0)} x_{i0} = K && \\
& \sum_{\substack{(i,j) \in A: \\ i \in S, j \notin S}} x_{ij} \geq
\lceil \frac{\sum_{i \in S} q_i}{Q} \rceil && \forall S \subseteq C, | S | \geq 2 \\ & x_{ij} \in \{ 0, 1 \} && \forall (i, j) \in A
\end{align}
(b) The capacitated VRP, as discussed in Lecture 3, for which the 2-index linear programming formu- lation (asymmetric) is provided in lecture Slide 8 of Lecture 3 is the starting point of this question. We will extend the problem as follows. A travel time τij is given for each arc (i,j) ∈ A. For each customer node i ∈ C , an earliest arrival time ai is given, arriving before ai implies that the vehicle needs to wait until ai to continue its route. For each customer node i ∈ C a latest arrival time bi is given, if a vehicle arrives before or at time bi, no penalty costs are incurred, however if a vehicle arrives after time bi a penalty cost of ρ per time unit late is incurred. The objective now consists of two components, namely, (1) the total travel cost, and (2) the total penalty cost for arriving at customers after their latest arrival time. The weights for each of these components are w1 for
P
Discrete Operations Research · 2023 - 2024
component (1), and w2 for component (2). How does the formulation in the lecture slides (Slide 8 of Lecture 3) need to be adapted to reflect the changes? Clearly define the new decision variables and write down the new objective and the additional constraint(s). You do not have to provide the complete formulation, you can only provide the new objective and the additional constraint(s). Make sure that your formulation is still linear.
Use the new decision variables ti ≥ 0 and li ≥ 0 ∀i ∈ C denoting the departure time at node i and the lateness at node i, respectively.
(c) Explain the impact of changing the values for the weights in the objective in question 2b.
Question 3 (50 points)
For this question, note the following:
• You must use the Python software code, which can be downloaded from the same Brightspace page as this assignment.
• The theory needed for this question is discussed in lecture 4 on December 4.
• There is an opportunity to work on this question during the tutorials on December 6.
We consider the following vehicle routing problem. There is a fleet of vehicles, stationed at a single depot (node 0). Each vehicle starts and ends its route at the depot, and each vehicle can transport a maximum of Q units. A set of n customers (nodes 1 through n) must each be visited once by one of the vehicles, making a delivery of quantity qi at customer i for i ∈ {1, . . . , n}. Traveling between nodes i and j incurs a travel cost cij, identical in both directions (symmetric). The objective is to minimize the total distance traveled by all vehicles by determining sequences of node visits for the vehicles. Note that this description so far is simply describing the standard symmetric Capacitated Vehicle Routing Problem (see lecture 3). In addition, a vehicle may only visit odd-numbered customers at odd-numbered positions in the route. And similarly, a vehicle may only visit even-numbered customers at even-numbered positions in the route. Furthermore, we set qi = 1 for all customer i ∈ {1,...,n}, so the maximum number of stops in a vehicle’s route equals Q.
Example. Suppose we have two vehicles and 10 customers, numbered 1, . . . , 10. And we assume each vehicle has a capacity of Q = 6. The customer visited first (that is, at position 1 in a route, so at an odd-numbered position in the route) can be either customer 1, 3, 5, 7, or 9. The customer visited second (that is, at position 2 in the route, so at an even-numbered position in the route) can be either customer 2, 4, 6, 8, or 10. And so on. Let us write the vehicles’ routes in a set of vectors (or in Python terms: in a " list of lists"). Each vehicle starts and ends at the depot, so each vector starts and ends with a zero. For example, the vehicle routes could be something like: routes=[[0,3,4,1,6,0],[0,5,10,7,2,9,8,0]]. This is a correct set of routes because (1) each route starts and ends at the depot (node 0), (2) each node is visited exactly once by a vehicle, (3) odd-numbered customers are at odd-numbered positions in the route, and even numbered customers are at even-numbered positions in the route, and (4) each vehicle visits Q customers or less, so capacity is adhered to. Note that Python lists are by default numbered from zero. So in the example, we have two vehicles: vehicle 0 and vehicle 1. And each visits a number of locations. Vehicle 0 starts at the depot: routes[0][0]=0, then goes to the first customer on the route, which is customer routes[0][1]=3, then on to the next customer routes[0][2]=4 and so on. Similarly, vehicle 1 also starts at the depot, visits a number of customers with routes[1][6]=8 being the last customer visited by vehicle 1.
Discrete Operations Research · 2023 - 2024
For this question of this assignment, you must create in Python a Simulated Annealing heuristic that can
find good solutions for this problem.
What you get (download from Brightspace): A fully functional implementation in Python of a Simulated Annealing heuristic for this problem. The software’s central component is the file “main.py”. From here, first instances (that is, the problems to solve) will be read from a file called “instances.csv” via the code in “convert_csv.py”. Next a simple greedy heuristic will create a feasible solution via the code in “generate_initial_routes.py”. Then this solution is updated during a certain amount of time, by trying various neighborhoods, and accepting (or rejecting) the found solutions (see lecture 4). For each candidate solution, the feasibility is verified (via the code in “check_feasibility.py”) and the objective value is determined (via the code in ”objective.py”).
What you must create yourself: A number of neighborhood operators that change the current solution into a new solution. Neighborhoods should be such that they generate feasible new solutions (the provided software has a built-in feasibility check, however, if your operators would generate infeasible solutions then evidently the solutions would not get any better). You create your own code for this in the file “neighborhoods_group_?.py”, where ? is to be replaced by your own group number. To facilitate your process, we have created one operator already as an example. So the software is fully functional. And all you need to understand from the software code to make this assignment is what you find in the file “neighborhoods_group_?.py”. Of course, it is presumably interesting to check out the whole code in all files, but it is possible to ignore all other files, and just work in “neighborhoods_group_?.py”. Furthermore, you can and should make some changes in the file “parameters.py”: you must add your group number on line 4 of this file, and you may change the other parameters in this file, for example, to run your heuristic on only one instance instead of all, to plot a route, or to change the temperature for the Simulated Annealing heuristic.
And finally: run your software code to solve the provided instances. As mentioned, the provided software is fully functional. If you run the software, it will determine solutions for a number of instances. The better the set of operators you create, the better the solutions will be. The final step for this question is that you run the software to create solutions for the given instances, using your operators. Solutions will be automatically written to the file “solutions_group_?.csv”. This file must also be handed in. The grade for this question will depend on the quality of the generated solutions.
What you must hand in for question 3 (with ? replaced by your group number):
• the file “neighborhoods_group_?.py” • the file “solutions_group_?.csv”
• the file “parameters.py”
After downloading the software code from Brightspace, before doing anything else:
• Open file “parameters.py” and at line 4 change the group num- ber to your own group number.
• In the file name of the file “neighborhoods_group_0.py”, change the zero to your own group number.
