Report#
Solving the problem with MILP#
Evaluate the small-size model output and answer [1.5 pt]:
Did the solver find an optimal solution? (yes/no)
How many Transfer Points were opened? (number)
What percentage of the total objective comes from: fixed establishment cost, transport cost, and emission penalty?
Answer: Yes, The small model (10 TPs, 15 zones) is very small for HiGHS. It should solve in <1 second and return optimal termination. The solving report will show the status as optimal.
Answer: six TPs are opnend.
Answer: Basically dividing fixed establishment cost (800), transport cost (185.15), and emission penalty (270.22) by objective value (1250.37)
What is the impact of changing value of \(\lambda\) on the number of open TPs, total fixed cost, total transport cost, and total emissions? Explain why these changes occur. Your explanation should relate to trade-offs between distance, emissions, and fixed facility cost. [3 pt]
Answer: Students should observe trends. Increasing λ means emissions are penalized more strongly, so the model is encouraged to reduce emissions even if doing so requires opening more TPs.
λ = 1 and 5:The model keeps the same configuration because emissions are penalized only moderately.
λ = 10: The model opens one additional TP to reduce emissions by shortening road distances.
λ = 15: The model opens yet another TP, further reducing distances and emissions.
More TPs are opened to reduce emissions, increasing the total establishment cost. Opening additional TPs reduces average last-mile distance, improving routing efficiency slightly.
More TPs = customers are closer to their serving TP → shorter roads legs → lower emissions.
Penalty grows linearly with λ, so even small emission reductions cannot offset a large λ.
Compare the small size and large size problems in terms of their computational time, number of opened TPs, and objective function value. What do these differences tell you about problem scaling? [1.5 pt]
Answer: The small instance solved very quickly, with a runtime of only 0.15 seconds, whereas the large instance required about 120 seconds (this could still be different on different systems but the order of difference should be relatively similar). This dramatic growth in computational time is expected: the larger instance contains more demand zones, more candidate TPs, and therefore many more continuous and binary decision variables, which significantly enlarges the problem search space. In terms of solution structure, the large instance opened 11 TPs, compared to 6 TPs in the small instance. This increase is natural: with more demand zones distributed across a wider area, more facilities are needed to satisfy capacity constraints and keep transport distances reasonable. The objective value also grew. Overall, the comparison shows how MILP models scale poorly as the number of locations grows: runtimes rise steeply, the model becomes harder to solve to optimality, and the resulting network design becomes more complex.
Solving the problem with GA#
What key solution property is lost when using GA instead of MILP? [0.5 pt]
Answer: The key solution property that is lost is the guarantee of optimality. A MILP solver such as HiGHS systematically explores the solution space and can certify that a solution is optimal or provide an optimality gap. This is while GA evaluates only a subset of the full solution space.
Is the GA a better algorithm to solve this problem compared to the MILP? Relate your answer to solve time and solution quality of the two methods. What do you think about larger size examples? [1.5 pt]
Answer: Based on the results from this assignment, the GA is not necessarily a better algorithm than MILP for solving this problem at the medium scale used here. In the large instance, the MILP solved to optimality in about 120 seconds, while the GA required roughly 100 seconds to converge to a fitness value of 1892.36, a solution that is close to, but not guaranteed to match, the MILP optimum. Depending on hardware and random initialization, the GA runtime can even exceed the MILP runtime. This illustrates that for problems of this size, MILP remains highly competitive. However, the main value of the GA is not in matching MILP performance for medium-size problems. Its strength becomes important for much larger instances, where MILP solvers struggle due to the exponential growth of binary decision combinations and rapidly increasing constraint sets. In such large-scale settings, MILP may become extremely slow, may fail to reach optimality, or may become computationally infeasible.
Change the population size of the GA (test 10, and 50) and evaluate how this affects run time and solution quality. [1 pt]
Answer: Changing the GA population size creates a direct trade-off between runtime and solution quality, which is exactly what we observe in the results. A small population explores the search space poorly. Fewer candidate solutions per generation means the algorithm has less genetic diversity and is more likely to get stuck in a local minimum. The computation is fast, but the solution quality degrades. A larger population increases diversity and allows GA to explore the space more thoroughly. This improves solution quality but increases the computational burden because more individuals must be evaluated in every generation.
By Nadia Pourmohammadzia, Delft University of Technology. CC BY 4.0, more info on the Credits page of Workbook