Monday, October 8, 2012

Pizza Delivery Routing Algorithm - A Pet Project

A couple months ago I realized that I had completely given up on my interest in web application development. I'd studied it briefly towards the end of my Master's curriculum a couple years ago, and had been meaning to reignite my interest through a couple projects. I'm not very gifted at web development, but I've seen enough to become interested. Alas, starting an MBA and getting married became greater (and worthwhile) time sinks.

The good news (for me and my interest) is that my wedding is on Saturday, which means I'll have some free time coming up. That, and I'm most of the way through the core MBA curriculum. Right now I'm taking a course in information systems management, which, if anything, is feeding my interest in restarting my hobby. My buddy Sam has been working on something for a couple years now, and his advice was simple: "Just do something, anything. Keep sharp."

My first project: pizza delivery routing algorithm. As I've mentioned before here, I used to deliver pizzas in high school and during college breaks. I developed a strange passion for operational efficiency after the business expanded and we had a new Point of Sale (POS) system installed. This was in 2004. My boss had no interest in even developing a website for the business at the time. He was mostly concerned with building the business one week at a time. But that didn't stop me from analyzing how inefficient some of our processes were - I was an engineering student, after all.

One of the major annoyances in operating a business with a personal delivery component (e.g. pizza) is figuring out how best to allocate your delivery resources (e.g. the drivers). My boss was notorious for taking guys off the clock if business was slow. The drivers figured this out quickly and gamed the system by taking as long as reasonably possible to complete a delivery during the slow down periods. It infuriated the boss, but he had to live with it.

On the flip side, when business was booming (e.g. during the dinner rush on a Friday night), we couldn't have enough drivers. Orders would run late because of the sheer backlog. Guys would make 2-3 trips per hour. Even with 15 drivers on the clock at once, we couldn't keep up. Drivers were motivated mostly by tips, and knew that getting the order to the customer sooner rather than later would result in a better tip. Drivers couldn't care less if the next order was late. This led to serious inefficiency. Whenever I was in charge of routing deliveries, I'd have guys wait a few agonizing minutes for any deliveries they could take in tandem based on geographical proximity - basically: if you have two orders going to Main Street in Trumbull (a 15 minute drive), have the driver take both even if they came in 10 minutes apart. It drove drivers, and my boss, crazy, but it resulted in fewer late orders on the whole. We would call these "two baggers" or "three baggers" - depending on how many orders went out (in warming bags).

I wished that the manual routing I had to do were somehow automated. I know there has to be something already out there now, but I figured my first project would be to develop something simple.

The interface should be straightforward: provide the user (e.g. manager) with a table of all open delivery orders grouped by recommended batch. A batch would be determined based on driving time for the round trip and would be temporal - you wouldn't batch two orders together that were ordered more than 35 minutes apart (for argument's sake). The idea is to provide the manager with a set of options to maximize the efficiency of each delivery driver at any one time.

The system would have to be flexible and optional. It would have to interface with the existing POS system to collect all open orders coming in. It should be optional because of various factors that come into play, especially driver skill. A manager probably wouldn't want to assign a long and expensive "three bagger" to the newest driver. The manager would have the option to break the orders into pieces. Therefore, the system would have the be "slave" to the POS system except, perhaps, if the manager decided to go with the recommendation and assign deliveries through it and have the POS system only become the "slave" in such cases. For example, if the system recommends a particular batch, the manager would select that batch, match it with a driver, and click "ASSIGN." The system would send the request to the POS system, which would assign those three orders to the driver.

I plan on using the MapQuest API for the background routing algorithm. There are many other options, but I found MapQuest's to be the most open for now.

There are a few tricky aspects that I'll need to take into account:

- Ensuring the correct address is entered. This would probably need to be tied in with the POS - the user may need to confirm the address with the customer.
- Tweaking the interface with the POS system to pull and push requests (timing, etc.). I'll have to make my own dummy POS for starters.
- Tweaking the algorithm to take other factors into account, like weather (doubtful) and performance parameters for drivers like average delivery time (maybe)

I doubt any business would actually pay for this, but it's a neat project. Maybe, just maybe, I could get a blurb in Pizza Today.

No comments: