GrabBro
GrabBro is a startup in the delivery industry. They realized that when people arrive in a new city and are staying at a hotel, one of the first things they need to do (but don't wish) is to buy groceries such as diapers and baby food, their favorite snack or drink, and other things that they can't find (or are too expansive) at the hotel.
To solve this problem, GrabBro provides a very convenient way for hotel guests to order grocery items without having to install new apps on their phones or signing up for services that they will likely use only once. All that guests need to do is to inform the grocery items they want. Then, a driver will bring it to the hotel lobby as quickly as possible and for a fair price.
To achieve that, GrabBro must be smart in how they get their drivers to buy the grocery items. Again, it has to be done cheaply and efficiently.
So, GrabBro created a database with grocery shops in the neighborhood of each hotel they serve. They also know which items are available in each shop and their prices. In addition, GrabBro has all the relevant routing information such as how long it takes to travel from Hotel A to Grocery B, from Grocery B to Grocery C, etc.
The problem then is, given an order, i.e., a list of items and the hotel where the guest is staying, how should GrabBro instruct a driver to buy and deliver the items?
In this example, we provide data for one instance of the problem that is for the Ibis Styles Goiania Marista hotel located in the Goiania city, Brazil.
We also provide four options of grocery shops and a grocery shop list with four items, along with the price (fictitious) of each item in each shop it's available.
Locations
| Location ID | Name | Type | Address |
|---|---|---|---|
| H | Ibis Styles Goiania Marista | Hotel | Rua 15 Quadra H24 Lote 07 09, Goiânia - GO, 74150-020 |
| S1 | Super Mauge | Grocery Shop | Av. Americano do Brasil, Qd 02 - Lt 1 - Vila Rizzo, Goiânia - GO, 74390-663 |
| S2 | Supermercado Royal | Grocery Shop | R. 610, Número 589 - Aeroviario, Goiânia - GO, 74435-280 |
| S3 | Supermercado Goiânia | Grocery Shop | R. U 82, 486 - Setor União, Goiânia - GO, 74313-740 |
| S4 | Supermarket Santa Genoveva | Grocery Shop | Av. São Francisco, 1003 - S - Santa Genoveva, Goiânia - GO, 74672-010 |
Shopping List
| Product ID | Product |
|---|---|
| GJ19 | Grape Juice (1l) |
| HM22 | Whole Milk (1l) |
| CP31 | Cocoa Ponder (250g) |
| P68 | Papaya (unit) |
Prices
| Shop ID | Product ID | Price (R$) |
|---|---|---|
| S1 | GJ19 | 10.08 |
| S2 | GJ19 | 11.28 |
| S3 | GJ19 | 8.52 |
| S1 | HM22 | 3.92 |
| S2 | HM22 | 5.00 |
| S3 | HM22 | 4.92 |
| S4 | HM22 | 3.96 |
| S1 | CP31 | 12.60 |
| S3 | CP31 | 15.96 |
| S4 | CP31 | 16.66 |
| S1 | P68 | 6.78 |
| S2 | P68 | 5.46 |
| S3 | P68 | 7.62 |
| S4 | P68 | 7.62 |
Transit Times
| Origin ID | Dest. ID | Distance (Km) | Transit Time (min) |
|---|---|---|---|
| H | S1 | 14.3 | 27 |
| H | S2 | 6.8 | 20 |
| H | S3 | 4.7 | 12 |
| H | S4 | 9.5 | 24 |
| S3 | S2 | 5.8 | 15 |
| S3 | S4 | 12.9 | 30 |
| S2 | S4 | 11.3 | 19 |
| S3 | S1 | 9.9 | 17 |
| S2 | S1 | 12.2 | 21 |
| S4 | S1 | 22.4 | 37 |
| S1 | H | 14.6 | 29 |
| S2 | H | 7.9 | 23 |
| S3 | H | 5.5 | 14 |
| S4 | H | 10.8 | 22 |
Let's assume that the driver departs from the hotel and the transit cost is R$0.30 per Km.
Which shop should each item be purchased from and which route should the driver take to minimize total cost?