Joseph Peterson

Plan a bakery’s deliveries

VROOM, an open-source route optimizer compiled to WebAssembly, plans a Seattle bakery’s deliveries in your browser. On a busy Saturday, it cuts 5 h 34 min of driving to 3 h 12 min.

Plan the day

VROOM saves 2 h 22 min of driving and 74.0 mi, 43% less.

Each van takes at most 19 of the 42 boxes: 1.3 times its share.

Which map
As the orders came in5 h 34 min148.8 mi, 3 vansLast van back after 2 h 53 min
Map of the bakery and 20 orders, with the routes of 3 vans dealt the orders as they came in. Shaded bands show driving time from the bakery, 5 to 30 minutes, with a line at 10 and 20. 12345671234567123456
Planned by VROOM3 h 12 min74.8 mi, 3 vansLast van back after 2 h 20 minFor the previous orders
Map of the bakery and the same 20 orders, with the routes VROOM planned for 3 vans. Shaded bands show driving time from the bakery, 5 to 30 minutes, with a line at 10 and 20. 12345678912345678912
Day
Vans

Tap a place on a map, or tick it in the list below, to add or remove its order. VROOM plans again each time.

Both plans for a busy Saturday, worked out in advance by the same solver. With JavaScript on, you can change the orders and the vans.

Driving time from the bakery, without traffic

  1. 5
  2. 10
  3. 15
  4. 20
  5. 25
  6. 30 min
  • Van A
  • Van B
  • Van C
  • Van D
  • The bakery
  • A place with no order
  • 10 and 20 min from the bakery

Map data © OpenStreetMap contributors

The same day, in time

Up is time. A van’s line leans while it drives and climbs straight up while it hands an order over, so the plan that keeps its vans out longer stands taller.

As the orders came inLast van back after 2 h 53 min
As the orders came in, in time: the map lies flat, time rises from it, and each van’s line climbs as its day goes on. The last van is back after 2 h 53 min.1 h2 h3 h
Planned by VROOMLast van back after 2 h 20 min
Planned by VROOM, in time: the map lies flat, time rises from it, and each van’s line climbs as its day goes on. The last van is back after 2 h 20 min.1 h2 h3 h

Drag a cube sideways to turn both, or focus one and use the arrow keys.

All 63 places
Orders
Stop by stop, both plans
As the orders came in
StopPlace and orderBoxesArrives after
Van A: 7 stops, 14 boxes, 1 h 39 min of driving, 41.9 mi
A1Hing Hay Park Pineapple buns, 2 dozen, 6 min from the bakery26 min
A2Judkins Park Brownies for a soccer team, 10 min from the bakery214 min
A3Ballard library Quiet cookies, 2 dozen, 13 min from the bakery240 min
A4Jefferson Park Hot cross buns, 18, 9 min from the bakery21 h 5 min
A5Kinnear Park Scones and jam, 18, 5 min from the bakery21 h 21 min
A6U District market Marionberry hand pies, 2 dozen, 8 min from the bakery31 h 37 min
A7Kerry Park 12 croissants with a view, 5 min from the bakery11 h 52 min
Van B: 7 stops, 15 boxes, 2 h 32 min of driving, 78.3 mi
B1Kubota Garden Mochi doughnuts, 2 dozen, 18 min from the bakery218 min
B2Gas Works Park 2 dozen maple bars for kite flyers, 8 min from the bakery245 min
B3Mercer Island library Palmiers, 3 dozen, 16 min from the bakery11 h 10 min
B4Alki Beach Beach-day snickerdoodles, 3 dozen, 18 min from the bakery21 h 39 min
B5Volunteer Park A tiered cake for a picnic, 7 min from the bakery32 h 5 min
B6South Park library Empanadas, 30, 15 min from the bakery32 h 26 min
B7Cal Anderson Park Rainbow sprinkle doughnuts, 2 dozen, 5 min from the bakery22 h 46 min
Van C: 6 stops, 13 boxes, 1 h 23 min of driving, 28.6 mi
C1International Fountain Mini cupcakes, 48, 3 min from the bakery23 min
C2Pioneer Square Coffee cake, 4 loaves, 6 min from the bakery214 min
C3Leschi Park Focaccia slabs, 3, 13 min from the bakery227 min
C4Fremont market Bagels by the baker’s dozen, 3 bags, 8 min from the bakery349 min
C5Golden Gardens S’mores bars for a beach fire, 19 min from the bakery21 h 6 min
C6Ravenna Park Rye loaves, 6, 10 min from the bakery21 h 27 min
Planned by VROOM
StopPlace and orderBoxesArrives after
Van A: 9 stops, 19 boxes, 1 h 3 min of driving, 21.1 mi
A1Ravenna Park Rye loaves, 6, 10 min from the bakery210 min
A2U District market Marionberry hand pies, 2 dozen, 8 min from the bakery316 min
A3Gas Works Park 2 dozen maple bars for kite flyers, 8 min from the bakery226 min
A4Fremont market Bagels by the baker’s dozen, 3 bags, 8 min from the bakery332 min
A5Ballard library Quiet cookies, 2 dozen, 13 min from the bakery243 min
A6Golden Gardens S’mores bars for a beach fire, 19 min from the bakery253 min
A7Kinnear Park Scones and jam, 18, 5 min from the bakery21 h 13 min
A8Kerry Park 12 croissants with a view, 5 min from the bakery11 h 18 min
A9International Fountain Mini cupcakes, 48, 3 min from the bakery21 h 23 min
Van B: 9 stops, 18 boxes, 1 h 53 min of driving, 49.4 mi
B1Pioneer Square Coffee cake, 4 loaves, 6 min from the bakery26 min
B2Hing Hay Park Pineapple buns, 2 dozen, 6 min from the bakery211 min
B3Leschi Park Focaccia slabs, 3, 13 min from the bakery223 min
B4Judkins Park Brownies for a soccer team, 10 min from the bakery232 min
B5Mercer Island library Palmiers, 3 dozen, 16 min from the bakery147 min
B6Jefferson Park Hot cross buns, 18, 9 min from the bakery21 h 5 min
B7Kubota Garden Mochi doughnuts, 2 dozen, 18 min from the bakery21 h 22 min
B8South Park library Empanadas, 30, 15 min from the bakery31 h 36 min
B9Alki Beach Beach-day snickerdoodles, 3 dozen, 18 min from the bakery21 h 58 min
Van C: 2 stops, 5 boxes, 16 min of driving, 4.3 mi
C1Volunteer Park A tiered cake for a picnic, 7 min from the bakery37 min
C2Cal Anderson Park Rainbow sprinkle doughnuts, 2 dozen, 5 min from the bakery215 min

How it works

The solver is VROOM 1.15.0, compiled from its C++ source to WebAssembly. It runs in a Web Worker in your browser, so planning sends nothing anywhere. The drive times come from OSRM’s car profile over OpenStreetMap roads, worked out once for every pair of the 64 places: 4,032 legs. They assume no traffic.

What VROOM is

VROOM is an open-source solver for vehicle routing problems. Give it places to visit, vans that hold so many boxes, and the time to drive between every pair of places, and it looks for the routes with the least total driving. The exact best plan takes far too long to find once there are more than a few stops, so VROOM builds a good plan quickly, then moves and swaps stops between routes until no change makes the day shorter.

What the colour bands are

Each band is an isochrone: the area a van reaches from the bakery within a set time. The band around the bakery is 5 minutes away, and each band after it adds 5 minutes, up to 30. A line marks where 10 and 20 minutes end on land. A band that reaches far along a road marks a fast road. A gap marks water, a park or a port with no street to drive. The list of places, the tables and the tip over each place give its drive time from the bakery as text.

The two plans

As the orders came in: the orders are dealt to the vans in turn, like cards, and each van drives its orders in the order they arrived, from the bakery and back. Planned by VROOM: the same orders and the same vans, with the total driving as short as VROOM can make it. Up to 30 orders, each stop on the map carries its number in its van’s run. Every van holds the boxes for 1.3 times its share of the day, so both plans fit, and VROOM still has to balance the loads. So a van’s room changes with the number of vans: the share does not.

In VROOM’s plans, one van drives the least, but it is back last. More vans finish the day sooner, which is what the line under each map shows: when the last van is back, handing over every order included. VROOM looks for the least total driving, not the earliest finish, so with more vans than the day needs it may leave one at the bakery, or give one a short run.

What it costs

Nothing to run. Every file is static, and your browser does the planning.

How it is built

VROOM is C++. Emscripten 6.0.13 compiles it to one WebAssembly file of 344 KB, gzip, which the page fetches only once there is something to plan. It runs in a Web Worker, so the page never waits on a solve. Only the solver’s own folder may compile WebAssembly: its files carry a Content Security Policy of their own, and no page’s policy allows it.

The drive times and the roads for all 4,032 legs between the 64 places were worked out once, from OpenStreetMap with OSRM, and ship as one file of 57 KB, gzip. Without JavaScript, the page shows the plans the build made by running the same WebAssembly in Node.

Credits

Map data © OpenStreetMap contributors, under the Open Database License. The places are public parks, gardens, beaches, viewpoints, libraries, markets and landmarks; the bakery and every order are made up.

VROOM is © Julien Coupey and contributors, under the BSD 2-Clause License. The licences of everything compiled into the solver are in LICENSES.txt.

Up and down to move, Enter to open, Esc to close