The traveling alesperson: an Oktoberfest routing adventure

We imagined a safe alternative to mark the occasion with a cold sip and a salty bite from the six local breweries that serve at Oktoberfest: Paulaner, Spaten, Hacker-Pschorr, Augustiner, Hofbräu, and Löwenbräu. 

Oktoberfest enthusiasts will responsibly wait until next year to gather for the traditional festivities in Munich, but there are certainly other opportunities like their virtual tours to keep the spirit alive. We brewed up a fictional contest that uses our very real routing capabilities. If you’d like to follow along, spin up a free Nextmv Cloud account

Congratulations, you’re a winner! You live in Munich, right? Perfect. You and five other winners will each host a few friends at your own mini Oktoberfest in one of six parks around the city. Each brewery will provide one park with beer and snacks of the winner’s choosing. 

Beer delivery basics: stops, precedence, and time windows

Enter the traveling alseperson, a twist on the original TSP (Traveling Salesman Problem), involving a few more stops and constraints. In fact, it’s more like traveling alespeople in a VRP (Vehicle Routing Problem), since we’ll have a few folks picking up and delivering treats from local breweries.

Let’s start solving! We’ll have 12 stops in total: 6 pickups from breweries and 6 deliveries to parks. Here’s what the stop at the Löwenbräu brewery looks like: 


"stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },

Of course, individual brewery pickups will need to be made before their counterpart deliveries at the parks. We’ll add the precedes constraint to handle this. Here’s what the Löwenbräu brewery stop looks like when we add that it must precede the Ostpark stop.


"stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "precedes": "Ostpark",
           },


Each brewery has its own set pickup time window where an employee will be available to meet the delivery person. Similarly, each park has a set drop off time window due to reservations that permit each party to enjoy their celebration during specific hours. We’ll add a hard window to each of the stops. 


"stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "precedes": "Ostpark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ] 
       },

Handling precious cargo: shifts, capacity, and compatibility attributes

Meet our alespeople! We’ll have four dedicated delivery folks, each on a scooter. These wonderful volunteers have other unrelated tasks to complete during the day, so we’ll add a shift start and a shift end for each vehicle. Note that if a constraint like speed applies to all vehicles or stop duration is the same for all stops, you can denote that in the defaults section.



"vehicles": [
       {
           "id": "scooter-1",
           "start": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T14:00:00-00:00",  
       },

Each brewery is sending one package (which includes beer and snacks). Each scooter can carry two packages. To make sure we’re not overloading the scooters, we’ll need to add capacities to each vehicle and quantities to each stop. Note that the stop ‘quantity’ is noted as a negative integer because it will reduce the remaining capacity of each vehicle. 


"vehicles": [
       {
           "id": "scooter-1",
           "start": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T14:00:00-00:00",
           "capacity": 2,     
       },
...
 
"stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "precedes": "Ostpark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "quantity": -1
       },

Each brewery has offered to provide the winner’s choice of hot or cold snacks. That’s right, we’re talking cold beer with warm pretzels, cheese spaetzle, Bismarck herring rolls, and more. 

Five of the six breweries will be sending hot snacks. Only one will be sending cold snacks. Each scooter has an ice box attached to the back. However, only two of the scooters also have a separate box that keeps items warm. 

Let’s take a look at the compatibility attributes for vehicles and stops. You’ll see that vehicles are able to carry multiple types of goods. Here we see that ‘scooter-1’ can carry refrigerated, heated, or both. Below, in the stops section, we see that the Löwenbräu brewery requires both refrigerated and heated delivery for their package.


"vehicles": [
       {
           "id": "scooter-1",
           "start": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T14:00:00-00:00",
           "capacity": 2,
           "compatibility_attributes": [
               "refrigerated",
               "heated",
               "refrigerated-heated"
           ]       
       },
 
...
 
"stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "precedes": "Ostpark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "quantity": -1,
           "compatibility_attributes": [
               "refrigerated-heated"
           ]
       },

The whole scenario — in one JSON file


{
   "defaults": {
       "vehicles": {
         "speed": 10
       }
     },
   "vehicles": [
       {
           "id": "scooter-1",
           "start": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T14:00:00-00:00",
           "capacity": 2,
           "compatibility_attributes": [
               "refrigerated",
               "heated",
               "refrigerated-heated"
           ]       
       },
       {
           "id": "scooter-2",
           "start": {
               "lon": 11.546951597433546,
               "lat": 48.13500294763079
           },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T14:00:00-00:00",
           "capacity": 2,
           "compatibility_attributes": [
               "refrigerated",
               "heated",
               "refrigerated-heated"
           ]        
       },
           {
            "id": "scooter-3",
           "start": {
               "lon": 11.542266448835239,
               "lat": 48.13941656515969
               },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T15:00:00-00:00",
           "capacity": 2,
           "compatibility_attributes": [
               "refrigerated"]
           },
       {
           "id": "scooter-4",
           "start": {
               "lon": 11.697995540610314,
               "lat": 48.144050871260994
               },
           "shift_start": "2021-09-25T12:00:00-00:00",
           "shift_end": "2021-09-25T15:00:00-00:00",
           "capacity": 2,
           "compatibility_attributes": [
               "refrigerated"
           ]
           }
 
   ],
   "stops": [
       {
           "id": "Lowenbrau",
           "position": {
               "lon": 11.556473881323726,
               "lat": 48.14777080261001
           },
           "precedes": "Ostpark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "quantity": -1,
           "compatibility_attributes": [
               "refrigerated-heated"
           ]
       },
       {
           "id": "Ostpark",
           "position": {
               "lon": 11.639107353112042,
               "lat": 48.115914505083516
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       },
       {
           "id": "Paulaner",
           "position": {
               "lon": 11.546951597433546,
               "lat": 48.13500294763079
           },
           "quantity": -1,
           "precedes": "Bavariapark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "compatibility_attributes": [
               "refrigerated-heated"]
       },
       {
           "id": "Bavariapark",
           "position": {
               "lon": 11.544422956457115,
               "lat": 48.13164410466503
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       },
       {
           "id": "Augustiner",
           "position": {
               "lon": 11.542266448835239,
               "lat": 48.13941656515969
           },
           "quantity": -1,
           "precedes": "Luitpoldpark",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "compatibility_attributes": [
               "refrigerated"]
       },
       {
           "id": "Luitpoldpark",
           "position": {
               "lon": 11.567005639043593,
               "lat": 48.16875988116286
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       },
       {
           "id": "Hofbrau",
           "position": {
               "lon": 11.697995540610314,
               "lat": 48.144050871260994
           },
           "quantity": -1,
           "precedes": "English Garden",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "compatibility_attributes": [
               "refrigerated"]
       },
       {
           "id": "English Garden",
           "position": {
               "lon": 11.608191491576118,
               "lat": 48.1647832966618
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       },
       {
           "id": "Hacker-Pschorr",
           "position": {
               "lon": 11.570485980432444,
               "lat": 48.11830211358586
           },
           "quantity": -1,
           "precedes": "Weissensee Park",
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T12:30:00-00:00"
           ],
           "compatibility_attributes": [
               "refrigerated-heated"
           ]
       },
       {
           "id": "Weissensee Park",
           "position": {
               "lon": 11.588494832047429,
               "lat": 48.10720190072625
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       },
       {
           "id": "Spaten",
           "position": {
               "lon": 11.554379727075645,
               "lat": 48.14570159344693
           },
           "quantity": -1,
           "precedes": "Westpark",
           "hard_window": [
               "2021-09-25T12:30:00-00:00",
               "2021-09-25T13:00:00-00:00"
           ],
           "compatibility_attributes": [
               "refrigerated-heated"]
       },
       {
           "id": "Westpark",
           "position": {
               "lon": 11.535019268758305,
               "lat": 48.12721131270343
           },
           "quantity": 1,
           "hard_window": [
               "2021-09-25T12:00:00-00:00",
               "2021-09-25T15:30:00-00:00"
           ]
       }
    ]
}

Beer is scooting across the city

And they’re off. If you’re following along, paste the JSON file above into the Nextmv Cloud console and click the “Run” button. In a few seconds you should see the routes on the map describing the trajectory of each of our alespeople on scooters. Success! All stops are assigned, and the goodies are on their way. 

If you click on the vehicle toggles in the console, you’ll be able to see the exact route of each of our alespeople. We can see that ‘scooter-1’ and ‘scooter-2’ are servicing more stops since they are the only ones that can carry both cold beer and hot snacks. 

Cheers

We hope all our fictional winners enjoy their mini Oktoberfests! Thanks for spending a few minutes thinking about beer and optimization with us. Grab a cold one and test out Nextmv Cloud for free.


Get the latest updates
Copy to clipboard
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Copy
Register to watch
Copy to clipboard
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Copy
Video by:
No items found.