Mini-Project for the Course “Optimization Theory, Methods, and Applications”: Vehicle Routing Problem
Mini-Project for the Course “Optimization Theory, Methods, and Applications”
Instructions:
1) Each student chooses one of the two mini-projects described below to accomplish. Each project has several tasks including modeling an optimization problem mathematically, using an existing algorithm and/or proposing a heuristic/metaheuristic algorithm to solve it, coding and testing the algorithm on 10 instances randomly generated. You can freely choose your programming language (C/C++, Python, etc.). One task in each project is optional, it is not obligatory to accomplish, but accomplishing the optional task will obtain a bonus of 20 points. Excluding the bonus, each project has 80 points.
2) Write a short report to describe the problem and its mathematical model, present the algorithm, and report the data of the instances and their solutions found by the algorithm.
3) In the report, all parameters and variables used in the model should be well defined and clearly explained, the procedure of the algorithm should be well presented as well as the way of generating the instances, their data and solutions.
4) The deadline for sending the report to the teacher via Mr 李恒 is August 31, 2022.
5) The plagiarism is prohibited. Any act of plagiarism may lead to a grade of zero point for the project.
Mini-project 1: Consider a single vehicle routing problem with profits in a transportation network with n + 1 nodes (n is a positive integer). A vehicle is initially located at node 0 which is its depot. It will visit a subset of n customers to collect profits. The n customers are located at node 1, 2, ..., n, respectively. Let N = {0, 1, 2, ..., n}. The distance, the traveling time, and the traveling cost from node i to node j are denoted by dij, tij, and cij, respectively for any i ÎN, jÎN. For simplicity, it is assumed that tij = cij = dij for any i and j. The time unit of tij is in minutes. The vehicle collects a profit of pi RMB yuan if it visits customer i, i ÎN\{0}. Each customer can be visited by the vehicle at most once. Because of the work duration restriction of its driver, the total travelling time of the vehicle cannot exceed T minutes. The problem is to find an optimal tour (a closed route) for the vehicle which starts from the depot node, visits a subset of the customers, and finally returns to the depot so that the net profit of the tour is maximized subject to the maximum duration constraint, where the net profit of the tour is defined as the total profit collected by the vehicle minus its total traveling cost.
1) Formulate the problem as a 0-1 mixed integer programming model. (30 points)
2) Randomly generate 10 instances with n = 20, i.e., with 20 customers, where the coordinates of the n + 1 nodes are randomly and uniformly generated from the square [0, 100]´ [0, 100], with the Euclidean distance between any two nodes, the profit pi of each customer i (i ÎN\{0}) is randomly generated from the uniform distribution U[pmin, pmax] with pmax > pmin, and the maximum duration T is randomly generated from the uniform distribution U[Tmin, Tmax] with Tmax > Tmin. You can set the values of pmin, pmax, Tmin, and Tmax freely, but the value of T generated for each instance must ensure that only part of the customers are visited by the vehicle in its optimal tour. (20 points)
3) Find the optimal tour for each instance by using the Solver of CPLEX or any other MIP solver (tool). (30 points)
4) Propose a heuristic or metaheuristic algorithm to the problem and find a near-optimal solution for each instance and compare it with the optimal solution found in 3). (Optional, 20 points)
Mini-project 2: Consider the inventory management of a single product in a retail store. The daily customer demand of the product is random and subject to a normal distribution with mean value m and standard deviation s. The customer demands in any two days are independent. In each day, if the product is out of stock (in shortage) in the store, unsatisfied customer demand will be lost. This store replenishes the inventory of the product from a supplier, i.e., obtains the product from the supplier. For simplicity, it is assumed that the replenishment lead time of the product from the supplier to the store is negligible (zero), i.e., the store can obtain the product immediately after it places an order to the supplier. This store uses an order-up-to level policy to manage its inventory of the product with the order-up-to level denoted by S. That is, at the end of each day, when the inventory level of the product, denoted by I, is below S, the store will order S – I units of the product from the supplier to bring its inventory level to S, and the S – I units will arrive at the store at the beginning of the next day. Two costs are incurred for the product at the store. One is inventory holding cost. At the end of each day, if the inventory level of the product, I, is positive, a holding cost of h´I is incurred, where h is the holding cost per unit of the product per day. On the other hand, in each day, if J units of customer demand of the product are not satisfied because of its shortage with J > 0, a lost sales cost of p´J is incurred, where p is the lost sales cost per unit of the product. To optimize the value of S, the store considers a planning horizon of T days. It wants to find the optimal value of S so that the expected total cost of holding and lost sales of the product incurred in the T days is minimized. It is assumed that the inventory level of the product is S at the beginning of the first day.
1) Suppose that this store adopts a scenario-based method for this stochastic optimization problem and consider N scenarios, where each scenario corresponds to a realization of customer demands in the T days in the planning horizon. Formulate the deterministic equivalence model of this problem. (30 points)
2) Set T = 30, h = 1, p = 19, s = cv ´ m , and generate 10 instances by randomly generating m from the uniform distribution U[100, 200] and randomly generating cv from the uniform distribution U[0.1, 0.4]. In addition, for each instance, randomly generate 100 demand scenarios according to the normal distribution N(m, s2), i.e., randomly generate dt,k according to this normal distribution, for t = 1, 2, ..., 30, k = 1, 2, ..., 100, where dt,k denotes the customer demand of the product in day t in scenario k. (20 points)
3) Find the value of S for each instance by optimally solving the deterministic equivalence model using the Solver of CPLEX or any other MIP solver (tool). (30 points)
4) Suppose that instead of minimizing the expected total cost, the store wants to minimize the total holding cost of the product in the planning horizon, subject to the constraint that the probability of shortage of the product at the end of each day does not exceed 0.05. Formulate this new minimization problem as a chance constrained programming model and transform it to a deterministic programming model. (Optional, 20 points)
