Advertising
Advertising

How heuristic software can save millions on transport costs

How heuristic software can save millions on transport costs

Any company that incurs transport related costs stands to benefit from ensuring their vehicles do their pickups and deliveries as efficiently as possible – both in terms of time and distance. And, while there are solutions out there that can help optimise routes, many businesses rely on a combination of human skill and software to ensure they are operating efficiently.

Humans, oddly enough, are actually very good at coming up with reasonable solutions to route optimization problems. We rely on “common sense” to ensure we don’t end up sending vehicles all the way across town because we intrinsically understand this isn’t efficient. Computers don’t have this built-in understanding of efficiency so they are quite bad at solving this type of problem.

Before we begin, however, let’s quickly define what we mean by “this type of problem”.

Multiple Traveling Salesman Problem

Imagine you have a bunch of salesman who have to visit a bunch of stops. What’s the most efficient way for them to visit all the stops? This is known as the multiple travelling salesman problem (mTSP). The mTSP is pretty famous in mathematics because it falls into a category of problem known as NP-Hard (Non-deterministic Polynomial Hard). One of the defining features of these types of problems is that it is not possible to know the solution unless you test every possibility.

Unfortunately, the number of possibilities in a very modest type of route optimization can quickly spiral out of control. Let’s consider a delivery company that has to make 60 stops with a single vehicle. To test every possibility, we would start by picking a point (initially we have 60 possibilities), then another (59 possibilities), and another (58 possibilities), and so on until we had stopped everywhere.

The number of permutations can be given by a function on your calculator called “bang” – it’s denoted by an exclamation mark. Since we have 60 stops, our equation for the number of permutations is given by:

60! = 60 x 59 x 58 x … x 3 x 2 x 1 = 8.32 x 1081

That’s a really big number. To put it into perspective, there are approximately 1080 hydrogen atoms in the entire universe. So in all the stars and planets and dust and gas in our solar system, in our galaxy, in the Andromeda galaxy, in our local cluster, in the entire super structure of all that exists, there are less hydrogen atoms than permutations in this seemingly simple problem. That’s why computers struggle with vehicle routing problems.

Optimizing routes

So humans are pretty good at working on this type of problem because we are able to take “common sense” shortcuts that end up giving us a pretty reasonable solution. The problem is that at some point even we become overwhelmed and simply can’t take into account all the factors required from modern businesses.

Imagine you had the task of creating a schedule for 10 vehicles, with 300 stops, over the course of a week, having to keep in mind that each stop is either a pickup or delivery (with a certain capacity – you can’t overload the vehicles), each location takes a certain amount of time, as does the trips between the stops, but your vehicles only run from 9am to 5pm, so there are time limits as well as capacity limitations.

Vehicles have different running costs – large trucks consume more fuel than lighter ones, but can carry more – they might also require drivers with specialized licenses who have a higher hourly rate. So you need to try and work out whether it is better to send a small vehicle a longer distance (bearing in mind that it can only visit a limited number of stops before its load capacity is reached), or send the larger vehicle because it also has capacity to deliver to other nearby stops.

But, each delivery takes time so the person creating the schedule also needs to ensure that the truck’s route doesn’t leave it miles away from the depot at 4:58pm – meaning that the driver ends up being furious that he or she will get home late. Vehicles also come with a built in range before they have to refuel, so you can’t assume they can drive indefinitely without building in time for refueling stops and driver breaks.

Advertising

What happens when some deliveries can only be made at certain times? If several locations require deliveries at the same time, the scheduler has to ensure that all the vehicles are delivering to those locations at the right time while still keeping the overall costs to a minimum.

Human optimizations

In the scenario above, the amount of work a human would have to perform is pretty daunting. Companies pay very smart people to generate their schedules ahead of time. It’s hard, specialized work that costs a lot of money.

But, to demonstrate how a human might approach this problem, let’s consider the following set of locations with two depots, each with a vehicle that has an operating time limit and a range limit (i.e. it may only travel 150Km per day). These limits, in the real-world, would depend on the unique resources and limitations of your own operation. But for now, here’s what we have:

70point-2vehicles

    Intuitively, we know that (unless there is a specific reason) sending the vehicle from the depot in south east (the orange marker towards the right of the map) to locations in the north west (top left of the map), near the second depot, is probably not going to be the most efficient way to do things. We might decide that it is a good idea to simply divide up the points roughly equally like this:

    70point-2vehicles-red-line

      From there it is up to us to try create the most efficient individual routes for each vehicle in order to produce the solution. I actually gave it a bash. It’s really not easy. Here’s what I came up (full disclosure, I had to get some help) shown in Google Earth:

      70point-2vehicles-googleearth

        Not bad, right? There are a couple of cross-overs in each tour, but this is because London is full of one-way streets and is crisscrossed with rivers that mean vehicles have to find nearby bridges, which can affect the course of their optimal routes.

        But there’s a problem. Neither of these vehicles’ tours come in at less than 150Km – one came in at 151.1Km and the other at 150.4Km. You might think I’m being pedantic but, for big operations that rely on efficiency, small differences have a habit of working their way up the chain to become big problems.

        Simply put, I couldn’t do it. From my perspective, this problem cannot be solved. Maybe people with a lot more experience and time on their hands can give it a go and see if it is possible. But, all is not lost. There are software applications that offer route optimizations available. I used one of these to try and improve on my solution.

        Advertising

        Computer optimizations

        Because of the massive complexity involved in trying to calculate reasonable solutions, mathematicians and programmers have become pretty sneaky in the way they approach things. They abandoned traditional programming techniques and began to use heuristic algorithms, which can produce pretty good solutions in a reasonable amount of time. A heuristic algorithm can look for solutions among many possibilities, but not necessarily guarantee it finds the best one.

        One example of a heuristic algorithms is called the Ant Colony Optimization (ACO), which mimics the way an ant colony forages for food. Initially ants head out in all directions. If an ant finds a food source it runs back to the nest leaving a trail of pheromones. When the next wave of ants set out, some are influenced by the weak pheromone trail and follow it. If they too come across the same source of food, they rush back to the nest, leaving a stronger trail of pheromones that influences the following waves of ants more and more, until eventually the ants make a nice straight line between the nest and their food source.

        By taking sensible shortcuts, implementing a few heuristic algorithms, and making a few assumptions here and there, computer scientists can create a system than can outperform even the best humans. I applied one of these to my problem and came up with this result:

        70point-2vehicles-computer-googleearth

          This is a better solution than I could manage, but it still broke the distance constraints of one of the vehicles – by less than 1Km. The other vehicle made it with a few hundred meters to spare.

          Ok, so we’re getting better. But this is a pretty simple problem. There aren’t delivery time windows, there aren’t vehicle and location constraints – i.e. does the vehicle need to have cold chain facilities, or be able to transport liquid volumes – or any of a myriad other potential stumbling blocks that might crop up in the real world.

          I did manage to run this particular problem on an enterprise system – to see if it is in fact possible.

          Enterprise optimizations

          There are significant differences in the quality of the solution between lightweight programs that use shortcuts (like basing cost calculations only on distance, or only on time) and built in assumptions (i.e. using human “common sense” to divide the map into areas each vehicle will deliver to), and ones that throw significant computing resources at complex real-world problems to produce unbeatable quality optimizations that genuinely produce significant savings on fuel, time, and costs.

          Instead of considering only distance or only time costs, enterprise systems must consider and measure both – just as both are factors in real world optimizations. A delivery truck might require two operators (i.e. a driver and an assistant to help unload) who work on hourly wages. This can have an impact on whether the system routes the vehicle via a shorter, but slower route, or a longer (but faster) one.

          Systems that only optimize the time taken, or the distance travelled, will never be able to get this fundamental balance of costs right because they only ever consider one or the other. Programs that use “common sense” shortcuts will also, by definition, miss out on potential solutions that aren’t intuitive to our minds – and there are many, many, many (uncountably many) of these.

          To generate our enterprise solution, I utilized Optergon, which is in use in over 60 countries around the world and integrates with transport, tracking and logistics companies via an API service. What makes Optergon interesting is that it doesn’t make use of so-called common sense shortcuts. Instead it relies on a combination of heuristic algorithms, including the ACO (mentioned earlier) and simulated annealing.

          Advertising

          Simulated annealing mimics the process of tempering steel, in which the metal is heated to get the atoms jiggling about with weaker bonds. The steel is then hammered forcing the atoms into a closer, more densely packed array as it cools. This process is repeated until the steel’s atoms are packed as tightly as possible.

          But cutting-edge algorithms and a system that teaches itself as it goes aren’t enough to tackle enterprise level problems on their own.

          Because of some curious features of the mTSP it is virtually impossible to avoid situations in which a solution “looks” great, but isn’t close to what the actual best solution looks like. This is what’s known as a “local minimum”, and is a tricky problem to overcome because you don’t know ahead of time whether the system has found a genuinely good solution, or a local minimum.

          In order to get around this, Optergon had to implement a massively parallel architecture that allows it to work on the same problem, and specific aspects of the problem, at the same time across hundreds of different processes. Sharing tidbits of information and gleaning new insight at every step of the way, Optergon’s individual processes make use of existing and proprietary heuristics to teach the overall system how to generate an unbeatable solution

          With all this in mind, our current problem turns out to be possible. Here’s the solution:

          70point-2vehicles-enterprise

            Solution courtesy of 3DTracking, integrated with the Optergon route optimization API

            In this solution, each vehicle arrives back at the depot within the bounds of the constraints set – one vehicle made it in 148.3Km, and the other in 147.9Km. Pretty tight, but valid.

            So why am I going on about the difference between a few kilometres? Well, for a start, you wouldn’t want a system that generates a magnificently cost effective solution that requires your vehicles to travel 2000 miles on a single tank of gas, carrying 30 tonnes of cargo that it doesn’t have capacity for, arriving at locations at the wrong time, and so on.

            An enterprise solution must produce the most cost effective solution possible within the real-world bounds dictated by the business. Which brings me to my next point…

            Not only did this optimization reduce our costs, it also showed us something we didn’t know before – whether or not it was actually possible to successfully visit all the locations within the given restraints. This makes a system like Optergon useful for determining whether or not it’s even possible to attempt certain things.

            Advertising

            A good example of where this is useful might be when transport companies quote for business. If they are able to run accurate optimizations on transport contracts before delivering a quote they can be much more accurate and competitive because they know exactly what is possible, and how much it will cost them.

            Comparing costs

            So, apart from the fact that two out of three solutions weren’t valid, what were the differences in cost? Bearing in mind that it is more important to produce a solution that is valid (i.e. possible within the constraints of the business) than a cheaper one that is not. It’s important to compare the distance and times provided by each solution as the cost is essentially an arbitrary reflection of these two components – for the sake of making the math a bit easier, I set the time and distance cost of $5 per hour and $5 per km respectively.

            Real businesses would need to input values that reflected their operation accurately in order to derive the correct costs – although, since the costs are the same for all three optimizations, we can also look at the percentage difference in costs to determine how much better one solution is over another.

            Human solution (with help) – Invalid

            Unit 1 (North west depot)

            • Distance: 151.1Km
            • Time: 35191 seconds
            • Cost: $824.41

            Unit 2 (South east depot)

            • Distance: 150.4Km
            • Time: 32480 seconds
            • Cost: $817.17

            Overall cost: $1641.58

            Computer solution – Invalid

            Unit 1 (North west depot)

            • Distance: 150.9Km
            • Time: 33856 seconds
            • Cost: $821.65

            Unit 2 (South east depot)

            • Distance: 149.8Km
            • Time: 34046 seconds
            • Cost: $816.63

            Overall cost: $1638.28

            Enterprise solution – Valid

            Unit 1 (North west depot)

            • Distance: 148.3Km
            • Time: 33142 seconds
            • Cost: $807.85

            Unit 2 (South east depot)

            • Distance: 147.9Km
            • Time: 34464 seconds
            • Cost: $807.50

            Overall cost: $1615.35

            In essence, the enterprise solution provided by Opteron produced a valid result that was in the region of 1.5% – 2% better than a human (with help), and a human using routing software. Although, this is a very simple problem and that gap would widen up quickly as more and more vehicles and stops were added – but 60 points was more than enough for me. For a company doing a few hundred locations a day, the improvements might be nearer to 10%, or 15%, depending on how good their existing optimizations are.

            Ok, so a couple of percent might not sounds like much. But, anyone who works in a logistics company and knows how much transport costs are would jump at the chance to shave entire percentage points off their costs. This might equate to millions of dollars being saved every year for even moderate sized organizations.

            Don’t forget about the fact that better route optimizations mean less distance travelled, which not only saves on fuel but also on labor and vehicle wear-and-tear costs. And fuel costs are only ever going to go up in the long run (assuming the global economy recovers at some point) so saving on fuel will become more and more of a financial imperative as time goes by.

            And, let’s not forget about the fact that if companies are travelling up to 10% less, then 10% less carbon is being pumped into the atmosphere. Not using enterprise route optimization is not only wasteful in terms of cost, it’s unnecessarily bad for the environment. Additionally, if you know ahead of time what the optimal way to perform your pickups and deliveries are, it means you also know how to pack the vehicles. Obviously, packing the vehicle is important because you don’t want to arrive at the first stop and have to unpack the entire truck to get at the first item to be delivered.

            If you know how to pack the trucks, you also now how to stock the warehouse so that the packers can operate as efficiently as possible, working quickly because everything they need is warehoused in a convenient location. In this way, having enterprise level route optimizations not only saves on transport but can also serve to maximize the efficiency of your operation up and down the chain, from the warehouse to delivery.

            Featured photo credit: Daniel Gimbert via flickr.com

            More by this author

            Pay Less & Save Money Shopping How to Pay Less Than 30% for Almost Anything Make money blogging I Made $1000 From a Single Blog Post, So Can You 17 Essential Free Online Resources for Entrepreneurs 8 Food & Drink Quotes For Women 3 Amazon Shopping Tips That Will Save You Money

            Trending in Product & Gadget

            1Check Out These 5 Air Purifiers If You Want Your Home Smelling Fresh 2Never Fall Asleep On The Wheel Again 3Misplaced Your Items? Get This Search Party 48 Important Factors of Website Development and Designing 57 of the Best Marketplaces for Website Flipping

            Read Next

            Advertising
            Advertising

            40 Top Productivity Apps for iPhone (2018 Updated)

            40 Top Productivity Apps for iPhone (2018 Updated)

            Over the years here at Lifehack, we’ve discussed plenty of apps that you can use to improve your overall productivity.

            There are certain ones that many of our contributors and editors (past and present) have adopted over the long-term — there are always the stalwarts that stick around. But there are also new apps that crop up every day, adding more and more depth to the app category.

            Some of the apps are incredibly plain and simple, while others are more robust and offer more features than you can shake a stick at. And everyone has the one they prefer.

            It’s been our job (and still is our job) to keep abreast of all of the productivity-type apps out there. As a result — and as a bit of a refresher — we’ve put together a list of 40 best productivity apps for iPhone to provide you with an all-in-one resource for you.

            Productivity apps to help you get things done

            1. OmniFocus

            This app is, while pricey, considered to be one of the (if not the) most robust and full-featured productivity apps on the market.

            Download it here.

              2. Forest

              Train yourself to put your phone down and stay focused on the task at hand by playing with this planting game. It’s fun and will help you achieve more.

              Download it here.

                3. Things

                Another robust choice, this app is a favorite amongst “productivityists”.[1]

                Download it here.

                  4. 30/30

                  Recently covered here at Lifehack

                  , 30/30 is a newcomer to the game that incorporates lists and timing of tasks into an elegant and easy-to-use interface.

                  Download it here.

                    5. Any.Do

                    A beautiful-looking app that is both easy on the eyes and your wallet.

                    Download it here.

                      6. PocketLife Calendar

                      This calendar app is specifically designed to be stylish and super easy-to-use. You can organize your life easily with different modern features.

                      Download it here.

                        7. Asana

                        We’ve covered Asana here at Lifehack

                        , and it is being actively developed by a strong team committed to making collaborative task management a more efficient and effective experience.

                        Download it here.

                        Advertising

                          8. ToDoist

                          This app keeps track of everything – from simple errands to your most important projects – so you can get it all done and enjoy more peace of mind along the way.

                          Download it here.

                            9. FlowTasks

                            From the folks at MetaLab, Flow is a gorgeous collaborative task management app that is easy-to-use and incredibly functional.

                            Download it here.

                              10. Calendars 5

                              This calendar app focuses on events that help you to keep track of upcoming events and tasks easily. It has everything you need to organize, track and complete your to-dos.

                              Download it here.

                                11. Clear – Tasks, Reminders & To-Do Lists

                                A fun and innovative list-making app that relies on swiping and pinching to make things happen. Clear created a lot of buzz when it launched, and might be the perfect to-do list gateway app for many.

                                Download it here.

                                  12. Due

                                  A robust reminders app that lets you store and maintain reminders of all types. It’s replaced Reminders for me when it comes to the basics, and it’s worth a look if you want to keep the mundane stuff out of your head and cluttering your mind.

                                  Download it here.

                                    13. Checkmark 2

                                    I use this app

                                    for location-based reminders (such as groceries I need to get or single items I need to pick up from various locations). Checkmark is simple to use and a valuable addition to my productivity arsenal.

                                    Download it here.

                                      14. TeuxDeux

                                      Created by Tina Roth Eisenberg and Fictive Kin — Teux Deux is simple and incredibly stellar in terms of design. If you like lists (including the popular “Someday Bucket”) and want to associate dates with tasks, then Teux Deux will be right up your alley.

                                      Download it here.

                                        15. Wunderlist 

                                        Another incredibly popular choice is Wunderlist. Part of 6Wunderkinder’s software family, it sports a gorgeous design and is incredibly functional. We’ve talked about the app a couple of times here at Lifehack, so check those posts out here.

                                        Download it here.

                                        Advertising

                                          16. Nirvana

                                          For the GTD enthusiasts, there’s Nirvana. Straight from the source: “Nirvana frees your mind to focus on actually getting things done. If you’ve had enough of generic to-do lists, it’s time for Nirvana.”

                                          Download it here.

                                            17. Priorities

                                            An elegant-looking task management app that has received decent reviews,[2] this could be the one for you if you’re not a fan of OmniFocus or Things — especially if you need (or want) to share tasks with others.

                                            Download it here.

                                              Productivity apps that help you build habits

                                              18. Productive

                                              With this app, you can plan your habits with an easy-to-use interface, schedule habits for any time of the day, set smart reminders for each time of the day and stay on track with useful feedback. This app is perfect for anyone who wants to build a habit that sticks.

                                              Download it here.

                                                19. Habitica: Gamified Taskmanager

                                                You can complete tasks and build habits in a more fun way with this app. Input your Habits, your Daily goals, and your To-Do list, and then create a custom avatar. Check off tasks to level up your avatar and unlock features such as armor, pets, skills, and even quests.

                                                Download it here.

                                                  20. Streaks

                                                  This app follows the model of the popular “don’t break the chain method” in that you use the app to track how you are donig in the pursuit of your goal. Great for goal-setting — and an easy and elegant interface to boot.

                                                  Download it here.

                                                    21. Remember The Milk

                                                    Another popular to-do list app, Remember The Milk has a huge following. It has plenty to offer, including the ability to share tasks with others.

                                                    Download it here.

                                                      22. Day One Journal

                                                      When it comes to journaling, nothing really beats Day One. Its latest update added a slew of features that will make you want to start making journaling a habit.

                                                      Download it here.

                                                        Productivity apps that makes organization easy

                                                        23. Evernote

                                                        Touted as the world’s most widely-used productivity app, Evernote an be used simply as a notetaking app or can be customized to be your GTD app of choice — among other things.

                                                        Download it here.

                                                          24. Pocket

                                                          You can save an article, video or link you want to read or watch later to Pocket from anywhere including your computer, Safari, email, and your favorite apps like Facebook, Twitter, Flipboard, and Feedly.

                                                          Download it here.

                                                          Advertising

                                                            25. Sync.Me

                                                            This app identifies unknown phone calls, warns you from annoying spam calls, and adds a caller picture to your contacts from Facebook, Twitter and Google+.

                                                            Download it here.

                                                              26. Droplr

                                                              One of the most popular file-sharing apps out there today. Straight from the source: “Stay productive on the go. Droplr for iPhone keeps you in sync and makes sharing on the iPhone natural.”

                                                              Download it here.

                                                                27. Dropbox

                                                                Before iCloud, there was Dropbox. And there still is Dropbox, which is still widely used by both Mac and PC users all over the globe. It’s like having a flash drive in your iPhone. A must-have.

                                                                Download it here.

                                                                  28. iDolly 

                                                                  In conjunction with Dolly Drive and DollySync, iDolly allows you to edit and share your documents from your iPhone.

                                                                  Since all your changes sync automatically to all your devices, the current version of a document will always be accessible because Dolly Sync keeps everything in sync. Very handy.

                                                                  Download it here.

                                                                    29. Soulver

                                                                    It may seem odd that a calculator app shows up on this list, but this is no ordinary calendar app. Ben Brooks over at The Brooks review describes Soulver as follows: “It is what calculators would have been if they were invented at the same time computers were, instead of what we have with most calculator apps.” [3]

                                                                    Download it here.

                                                                      Productivity apps that help you work smart

                                                                      30. Captio

                                                                      A simple capture tool. Straight from the developers: “It’s simple. Open Captio and start typing. When you’re done, hit Send. The note is immediately delivered to your email inbox.”

                                                                      Download it here.

                                                                        31. Drafts

                                                                        A tremendous capture tool that allows for simple capture, followed by sending items to various applications such as OmniFocus, Things and more.

                                                                        Download it here.

                                                                          32. NoteShelf 2

                                                                          This is a perfect note-taking app for you. You can take beautiful handwritten notes, type, annotate PDFs, record audio & create lists. You can organize them into categories or groups.

                                                                          Download it here.

                                                                          Advertising

                                                                            33. Doodle

                                                                            This app links directly with the Doodle service, which is one that allows you to plan and organize meetings far more efficiently and effectively. Lifehack contributor Steve Dotto has written about Doodle more in-depth here.

                                                                            Download it here.

                                                                              34. TextExpander (Legacy)

                                                                              I have saved countless hours of time with TextExpander, and despite its inability to be as robust on iOS as it is on the Mac, it is still a worthy app to have in your arsenal.

                                                                              Download it here.

                                                                                35. Launch Center Pro

                                                                                A quick launcher for the iPhone that doesn’t just launch an app…with some of them it can do much more. This app saves you time by launching complex actions in a single tap.

                                                                                Download it here.

                                                                                  36. GoodReader

                                                                                  This may seem to be an odd one to make this list, but here are plenty of reasons why it is here with this article.

                                                                                  Download it here.

                                                                                    37. LogMeIn

                                                                                    Want to be able to control your Mac from wherever you are? Then get this app.

                                                                                    Download it here.

                                                                                      Productivity apps that improve security

                                                                                      38. 1Password

                                                                                      There is simply no better password manager out there. I’ve even put together a 1Password Emergency Kit worth looking at here.

                                                                                      Download it here.

                                                                                        39. LastPass Password Manager

                                                                                        You can store passwords and logins, create online shopping profiles, generate strong passwords, track personal information in photo and audio notes.

                                                                                        All you have to do is remember your LastPass master password, and LastPass autofills web browser and app logins for you.

                                                                                        Download it here.

                                                                                          40. Truecallers

                                                                                          Identify and block spammers, search for unknown numbers and call friends easily with this app. With a community-based spam list from over 250 million users, you’ll need this app.

                                                                                          Download it here.

                                                                                            There are plenty of other options out there (and we’ve heard from readers in the past as to what they enjoyed using), but these 40 are among the best.

                                                                                            Reference

                                                                                            Read Next