Excel File: HomeworkAssignment2.xlsx Directions: There are two questions in this assignment, each consisting of several parts. Some require completion of Excel sheets with formulas and/or optimization models, and some require solving a probl
SCMA455 – Assignment #2
Winter 2025
Due Date: April 1, 2025
Excel File: HomeworkAssignment2.xlsx
Directions: There are two questions in this assignment, each consisting of several parts. Some require
completion of Excel sheets with formulas and/or optimization models, and some require solving a
problem by Excel, Concorde TSP solver, or VRP Solver. You can consult the instructor at any time, if any
part of the questions is not clear.
Submission: Complete the Excel file and prepare a report as instructed in the questions below. Submit
your report in PDF format and the Excel file via D2L. Name your pdf report as “HWAssignment2_GrXX.pdf”
and the Excel file as “HWAssignment2_GrXX.xlsx” where XX is your group number. Hard copy or e-mail
submissions are not accepted. Upload all the input text files that you created to run Concorde and VRP
Solvers.
Question 1. (50 Points) Sobeys is a Canadian Supermarket Chain headquartered in Stellarton, Nova Scotia.
They operate under a variety of banners including Sobeys and Safeway, which are their leading brands in
Calgary. Table 1 in the Excel file provided with this assignment contains the names and addresses of their
23 stores as well as the location of the Distribution Center that supplies fresh produce to these stores.
You will also see the expected daily demand of each store in Table 1. Currently, fresh produce is delivered
on a daily basis with a Class 6 truck that has a payload capacity of 5,000 kgs. This truck leaves the
Distribution Center in the morning, visits each store, and returns to the distribution center.
1
Answer the questions below and prepare a report that contains your answers. For bulky information (eg.
the sequence of the cities in a tour), you can refer to the Tables in your Excel file if you find it difficult to
insert in your report. See Remarks below for supplementary information to complete each part.
a) (3 Points) Find the coordinates of each location by using Google Maps and enter them in Table 1. (See
Remark 1.)
b) (3 Points) Estimate the distances in kilometers between each pair of stores by using rectilinear metric
and fill the from-to distance matrix in Table 2. (See Remark 2.)
c) (5 Points) Starting from the node numbered as your group number; find a feasible TSP tour with the
Nearest Neighbor (NN) heuristic manually. Write the tour you found in cells K33:AH33 of Table 3. (See
Remarks 3 and 4.)
d) (5 Points) Use the corresponding Excel Macro provided for Lab Session 3 to find a feasible TSP tour by
the specified heuristic for your group in cell J34. Enter the resulting tour in Table 3 in the designated
row (cells K34:AH34). (See Remarks 3, 4, and 5.)
e) (4 Points) Use the VRP Solver to find a single tour. Note that this will be another feasible TSP tour for
the Class 6 truck since its capacity is more than the total payload to be delivered. Do not enter any
distance limit to force the algorithm to produce only one tour. Enter the resulting tour in Table 3 in
the designated row (cells K35:AH35). (See Remark 6.)
1
All the information given in this question except the locations of the stores are fictional and created for educational
purposes and the sake of this problem.
f) (5 Points) Use Concorde TSP solver to find the optimal TSP tour for this problem. Insert the email you
received from NEOS server in your report. Enter the optimal tour in Table 3 in the designated row
(cells K36:AH36). (See Remark 7.)
g) (5 Points) Fill in Table 4. Enter the tour lengths of each tour you reported in Table 3. Make sure that
the tour lengths are in kilometers. Write a formula in cells AM33:AM36 to calculate the percentage
deviation of each heuristic solution from the optimal length (reported in Cell AL36). Use two decimal
points and format the cells to show the numbers in %.
h) (4 Points) If the average speed of this truck (including stops in the traffic and the waiting times for
unloading at each store) is 12 km per hour. How long would the optimal tour take? What is the
utilization of the truck?
i) (8 Points) Considering that a single tour can cause several stores to receive their demand quite late
during the day, Sobeys logistics team is considering switching to Class 4 trucks with a payload weight
of 1600 kilograms. The average speed of these trucks will be 20 km per hour, and the total trip
duration (from depot to depot) should not exceed 3 hours to avoid any afternoon deliveries. Use VRP
solver to fill out Table 5. You can add columns or rows if necessary. (See Remark 6.)
j) (8 Points) Compare the current scenario in which a single Class 6 truck is used for distribution and the
proposed scenario with Class 4 trucks in terms of their implications on Sobey's logistics operations.
Remarks:
1. When you click on a location on Google Maps, the latitude and longitude will appear on the bottom of the
screen. Coordinates of one of the stores is already given.
2. One (“1”) unit distance on the geographical coordinate system corresponds to approximately 72 kilometers. For
example, if the coordinates of two points are
(
푥
1
,푦
1
)
and
(
푥
2
,푦
2
)
, respectively, then the distance between
these two points should be estimated as (
|
푥
1
−푥
2
|
+|푦
1
−
2
|)×72 kilometers with Rectilinear metric. You
must use the “VLOOKUP” function with an appropriate absolute/relative referencing in Table 2 to retrieve the
coordinates of the stores from Table 1. Cell K5 must contain the correct formula, and the rest of the cells in
Table 2 should be propagated (with Fill Right and Fill Down commands) from this cell.
3. If your group number is 3, then cell K33 should contain 3 as the starting node and cell AI33 should also contain
3 as the ending node. Note that the truck leaves the distribution center in the morning and returns to the same
location. So, the TSP tour that is implemented in practice starts from Node 0 and end at Node 0. However, this
does not prevent you implementing a TSP heuristic with any arbitrary starting node. Suppose that there are 5
nodes in your problem where node 1 is the depot for the trucks. You implement a Nearest Insertion Heuristic
with a start node of 3 and you find the following tour: 3 – 2 – 4 – 1 – 5 – 3. Note that this tour is equivalent to
the 1 – 5 – 3 – 2 – 4 – 1 tour, which will be implemented in practice. Therefore, solving a heuristic algorithm
with a node different than the node for the depot still provides a valid tour to be implemented in practice.
4. The heuristics in Excel macros only use positive values for the coordinates. Therefore, you should enter the
absolute values of the longitude when running these heuristics. For example, rather than entering -114.098973,
you should enter 114.098973.
5. Let 푋be your group number. If (푋MOD 3) = 0 then use Cheapest Insertion Algorithm, (푋MOD 3) = 1 then
use Farthest Insertion Algorithm, if (푋MOD 3) = 2 then use Nearest Insertion Algorithm. If you do not use the
correct algorithm, then you will receive zero points from the corresponding question.
6. When using the VRP Solver, you must load the distances you calculated in Table 2 with a text file since this
software does not have a rectilinear metric option. Use the following screen to accomplish this:
Use the following options when using the VRP Solver:
7. Input the coordinates of the stores as integers for Concorde solver. For example, if you identified the coordinates
of a store as (-114.098973, 51.132748) then enter these coordinates as (-114098973, 51132748) in the input file
for the Concorde solver. The coordinates must have six decimal points before you make the integer conversion.
This means that you should add a zero in the millionth decimal before the conversion, or equivalently, append
a zero at the end of the integer number after the conversion, if necessary, to make the x-coordinate a 9-digit
number and the y-coordinate an 8-digit number.
Question 2. (50 Points) Lactalis Finland Oy (LFO), a giant beverage reseller of Finland, has decided to enter
the European beverage market with their specialty power and healthy drinks. Rather than opening
facilities in a piecemeal fashion, the company has decided to develop an overall location strategy for its
distribution centers (DCs). The DCs will be replenished by LFO's main Finnish supplier which produces the
drinks. Products will be shipped to local wholesalers throughout Europe. LFO is considering five candidates
DCs that will distribute products to nine local wholesalers. The distances between each DC and wholesaler
and the demand at each wholesaler (in 1000 cases per year) are given in the tables below. The unit cost
of transportation from Cologne and Kiev to any other wholesaler location is $0.22 per every 1000 cases
carried for one kilometer. The same cost from Lyon, Nitra, and Turin to any other wholesaler location is
$0.12. Your team has been hired as a consultant to help LFO in making their DC location decisions. Prepare
a report that presents your answers to the questions below. Tabulate your results whenever appropriate.
Make sure to capture the cost and other operational implications of each alternative. Try to stick to the
templates we covered in the lab session. The Excel file that you submit must include all completed tables
and optimization models working properly.
From-To Distance Matrix (km)
Local Wholesalers
Distribution
Centers
Toulouse Toledo Graz Liege Brighton Minsk Sofia Sarajevo Copenhagen
Cologne 1172 1835 894 133 634 1650 1904 1473 759
Kiev 2923 3753 1515 2006 2458 567 1313 1679 1788
Lyon 538 1306 1121 681 970 2269 1850 1468 1507
Nitra 1849 2617 352 1188 1689 1163 921 694 1202
Turin 765 1541 815 991 1276 2181 1544 1162 1553
Demand (in 1000 cases per year)
Toulouse Toledo Graz Liege Brighton Minsk Sofia Sarajevo Copenhagen
6,500 2,500 3,500 4,800 1,600 5,500 3,600 8,000 7,000
In parts (a) and (c), assume that the supplier will not charge for transportation when replenishing the DCs
of LFO.
a) (10 Points) Find the total distribution costs when 푝DCs are opened, for 푝∈
{
1,2,...,5
}
. Create a graph
of the number of DCs opened vs. total shipping costs. For each value of 푝, state the optimal locations
for the distribution center(s) opened and the demand points served by each DC. Assume that there
are no capacity restrictions on the DCs and distribution links. Develop and implement your model in
“Question 2. (a)” sheet of the Excel file.
b) (5 Points) How many distribution centers would you recommend LFO senior management to operate
with, based on your findings of part (a)? Explain.
c) (15 Points) You ask LFO's senior management whether they can provide you with the fixed costs of
opening the DCs and their operating costs, as well as what would be the operating capacities of the
DCs. They tell you that you are the consultant, not them, so you should estimate these values. After
careful analysis, you collect the following additional information. The fixed cost of opening and
operating a distribution center (including construction, equipment, etc.) and the variable operating
costs differ from location to location due to the differences in land and labor costs. The following table
summarizes the estimated cost parameters based on designed capacity of 35,000,000 cases per year:
Distribution
Centers
Fixed Cost of
Opening a DC
*
Variable Operational Costs per 1000
units of Items Processed in DC per year
Cologne
12,000,000 3.0
Kiev
5,000,000 1.2
Lyon
20,000,000 3.0
Nitra
5,000,000 0.8
Turin
10,000,000 3.0
*
Expected useful life of the facility is 15 years. Money is valued at 8%.
Determine how many distribution centers LFO should open, where they should be located, how much
capacity should be allocated to each distribution plant, and which wholesalers should be supplied
from which distribution center so that LFO can minimize the total annual costs including the fixed and
variable costs of opening and operating a DC and transportation costs. Develop and implement your
model in “Question 2. (c)” sheet of the Excel file.
d) (5 Points) What are the utilization rates (ratio of utilized capacity with respect to available capacity)
at each distribution center? What can you suggest LFO based on these values and the designed
capacity of each DC?
The main supplier of the beverages has approached LFO and inquired whether LFO would be willing to
purchase their plant in Turku, Finland. Since LFO has strong faith in the future of their European
operations, they are seriously considering this offer. The LFO management now wants you to analyze the
impact of this potential purchase on their decisions regarding the DCs.
e) (12 Points) The distances between the Turku plant and each DC in kilometers are given in the following
table.
Cologne Kiev Lyon Nitra Turin
2872 1770 3495 2392 3456
Assume that the cost of transportation from the plant to the distribution centers is $0.1 per kilometer for
each 1000 units carried. Find the optimal locations of distribution centers to be opened under this new
Note that the transportation costs from the plant to the DCs should also be counted for in this scenario.
analysis. Report the overall minimum cost, the distribution centers to be opened, and which wholesalers
should be allocated to which DCs. Develop and implement your model in “Question 2. (e)” sheet of the
Excel file.
f) (3 Points) Compare the solutions of parts (c) and (e)? Which one should be preferred?