SEEM5650 Integer Programming Spring 2024 Assignment 2
Instructions
SEEM5650 Integer Programming
Spring 2024
Assignment 2
Due: April 25, 2024 at 3:00 pm
To submit your answers, please zip all your files, and upload the file to Blackboard. Please name your file as Assignment2-SID.zip (where SID is your student ID). Answers to the prob- lems must be typeset by using a text editing system such as LATEX. It is preferred to code the heuristics in C++. You are not allowed to use the pre-existing toolboxes/packages for the implementation. All solutions obtained from the computational study in Problem 4 need to be saved and included in your submission.
The University is very serious about academic honesty. If you adopt someone’s ideas or paraphrase someone’s writings (including class notes), you must provide citations in the text and references at the end of the report. A reference at the end without a citation in the text is not acceptable.
Background
CU Logistics is a company specialized in the last mile delivery service. Due to a large amount of packages that need to be delivered, CU Logistics employs contractors to deliver the packages to its customers. The contractors use their own vehicles when delivering to the end customers. Each contractor meets up at the depot, loads his/her vehicle with packages, then deliver the packages to a subset of the customers. It is not necessary for the contractor to return to the depot after servicing the last customer. The company has a strict policy about not to overload the vehicles. Hence, a vehicle may not be loaded with more than its capacity. It is assumed that all vehicles have the same vehicle capacity. Contractors are paid based on the total mileage they have driven (starting from the depot and ending at the last customer). Due to company policy, the total mileage a contractor has to drive cannot exceed an upper bound. The manager of CU Logistics would like to know which customers each contractor should visit, and the order in which each contractor should visit them so that the total mileage is minimized.
Problems to address
-
Give an integer linear formulation of the above problem. Explain the decision variables, objective function, and the constraints clearly.
-
Implement a greedy construction heuristic for solving the above described problem. Provide an algorithm of the heuristic and explain the different steps of the heuristic.
-
Improve the solutions obtained from Problem 2 by implementing a tabu search heuristic. Provide an algorithm of the heuristic. Explain the neighbourhood operator(s) used, the different steps of the procedure, and how the parameter values are set.
-
Conduct an experimental study on the 24 instances. For each of the instances, report the solution value of the best feasible solution encountered in Problem 2 and Problem 3, and CPU time needed for running the algorithm.
1
