Al-Salem Supermarkets is in the process of expansion in the western area of Saud

Question

Al-Salem Supermarkets is in the process of expansion in the western area of Saudi Arabia. During the next year, Al-Salem is planning to construct new stores that will serve 10 geographically dispersed communities. Past experience indicates that a community must be within 25 kilometres of a store to attract customers. In addition, the population of a community plays an important role in where a store is located, in the sense that bigger communities generate more participating customers. The following tables provide the populations as well as the distances (in km) between the communities: Formulate an ILP that can find the least number of stores (and their corresponding locations) to be constructed, taking into account the distance restriction and the concentration of populations. (Bonus 5 points: Solve the problem using AMPL).

Explanation / Answer

Formulation as an Integer Linear Programming problems.

The problem is about finding the least (minimum) number of stores and thei locations to be constructed, taking into account the distance restriction and the concentration of populations.

Let Xi (binary) represents the decision variable having the value 1 if a store is constructed at ith location otherwise its value is zero.

Let Xij (binary) represents the condition taking the value 1 if jth community is (within 25 kilometers) served by store at ith location otherwise takes the value zero. The resultant matrix based on the given distance matrix is as follows:

Solution using Excel solver shows Three stores at Location2, Location6 and Location10 as follows:

Store at location2 can cover communities at 1, 2, 3, 7, and 8; store at location6 can cater to communities at 1, 3, 5, 6,7, and 8 whereas store at location10 may be used by communities at 1, 4, 9, and 10 and size of populations are as above.

FromTo L1 L2 L3 L4 L5 L6 L7 L8 L9 L10 Population L1 1 1 0 0 1 1 0 0 0 1 10000 L2 1 1 1 0 0 0 1 1 0 0 15000 L3 0 1 1 0 0 1 0 0 1 0 28000 L4 0 0 0 1 0 0 1 1 0 1 30000 L5 1 0 0 0 1 1 0 0 1 0 40000 L6 1 0 1 0 1 1 1 1 0 0 30000 L7 0 1 0 1 0 1 1 0 0 0 20000 L8 0 1 0 1 0 1 0 1 1 0 15000 L9 0 0 1 0 1 0 0 1 1 1 60000 L10 1 0 0 1 0 0 0 0 1 1 12000

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.