The World News publishes and delivers a morning newspaper 7 days a week. The bun

Question

The World News publishes and delivers a morning newspaper 7 days a week. The bundled papers are delivered by trucks to a number of area communities where they are picked up by carriers at a central location in the community, who then deliver the individual newspapers to customers along various predetermined routes. The papers arrive at the central distribution location around 6 A.M., and they must be delivered by 8 A.M. The routes include homes, stores, restaurants, and newspaper machines. One community, David, has 5 routes, and six available paper carriers, who have requested a delivery contract. The following table shows the time (in minutes) required to deliver the newspapers along each route, the number of papers delivered on each route, and the vehicle capacity (in number of papers) of each carrier:

Formulate an integer/binary programming model that will minimize the total number of carriers needed to make the deliveries and that will determine which carrier will be assigned each route and the total number of papers delivered by each of the selected carriers. (Only formulate, dont need to solve)

Carrier A BC D EF Vehicle capacity 600 720 450 510 660 550 Route 1 2 3 4 5 6 7 Time (min.) 29 3515 35 20 23 35 Papers delivered 200 240 110 90 65 135 80

Explanation / Answer

Let us define the decision variables;

Decision Variables:

C1 to C6 - Carrier assignment variable (binary)

Xij - if i route to be catered by j carrier (if assigned 1 in binary variable)

Objective Function:

Our objective is to minimize no. of carriers assigned

Minimize C1 + C2 + C3 + C4 + C5 + C6

Subject to Constraints:

1. All routes are to be assigned to at least one carrier;

X1A + X1B + X1C + X1D + X1E >= 1

X2A + X2B + X2C + X2D + X2E >= 1

X3A + X3B + X3C + X3D + X3E >= 1

X4A + X4B + X4C + X4D + X4E >= 1

X5A + X5B + X5C + X5D + X5E >= 1

2. Capacity constraint

Every carrier has a rated carrying capacity and hence cannot carry more than the rated capacity to cater the demand of the routes,

For Carrier A,

200X1A+ 240X2A+ 110X3A+ 90X4A+ 65X5A <= 600C1

Form the similar equation for routes B, C, D, E and F

3. Time Constraint:

Time required for delivery on all the routes assigned should not exceed 2 hours (6 am to 8 am)

For Carrier A,

29X1A+ 35X2A+ 15X3A+ 35X4A+ 20X5A <=120

Similarly, form the equations for the other carriers B, C, D, E and F

Screenshot of the same problem formulated in Excel;

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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