Posts

Mitigation by Iteration

Mitigation by Iteration – Facilitating the Optimisation Journey

/0 Comments/in , , , , /by

For companies to remain competitive, they require smart systems that solve their unique day to day business problems. However, when applying these systems many decision makers get lost in the complexity due to limited communication and collaboration within the implementation process.

We are at the cutting edge of the latest optimisation methodologies and web technologies. However, unlike many other optimisation, and analytics companies out there, one of our main goals is to make powerful optimisation accessible in the real world to bring value to our clients.

We specialise in the development of web applications and smart optimisation engines– delivered in less time than you would probably think. It’s not unusual for us to go from an initial workshop with a client, to understanding their problem, and then having a fully functional optimiser in a production environment within three months.

On top of this the same people are often involved through the entire SDLC (software development life cycle) i.e. from the spec/design, theory, implementation and delivery/support. This reduces the overhead many organisations incur by having different people in business analytics and developer positions. The people implementing the solution actually understand and work with you to solve your problem.

Read more

Optimisation: Striking the Right Balance

/0 Comments/in , , /by

One of the guiding principles we use in commercial mathematics is to “Model Conservatively, but Optimise Aggressively”. This means that the problem domain should be modeled with sufficient “fat” in the data to ensure that the results are both legal and robust; but given this, we should then seek to apply the best (fastest and highest quality) solution approach that we can get our hands on.

Optimising aggressively can sometimes have it’s downfalls, though, if taken too literally. I’ve been doing a few experiments with numerical weightings of the objective function in a Vehicle Routing problem, where this issue is readily apparent. (Actually it is a Vehicle Routing problem with time windows, heterogeneous fleet, travel times with peak hours, both volume and weight capacities, and various other side constraints).

Our Vehicle Routing uses travel times (based on shortest paths through the street network) that are characterised by distance and duration. Durations can vary due to different road speeds on different types of streets (highways vs suburban roads for example). This leads to the question of how (on what basis) to optimise the vehicle routes – given that the optimisation has already to some extent minimised the number of vehicles and created well-clustered routes – what is the most desirable outcome for KPIs in terms of duration and distance?

In one experiment I’ve tried three different weightings for the duration (cost per hour) while keeping the cost per distance constant. I’ve run three values for this cost per hour – low, medium, and high weightings – on real-life delivery problems across two different Australian metropolitan regions.

Region 1
Total Duration Driving Duration Distance
Cost/hour
Low 74:47 24:38 708
Medium 72:45 23:55 712
High 72:58 23:42 768
Region 2
Total Duration Driving Duration Distance
Cost/hour
Low 113:54 46:44 1465
Medium 107:51 41:36 1479
High 108:51 43:49 1518

From these results, there is a (more-or-less) general correspondence between distance and the driver cost per hour as you would expect. However, if you push one weighting too far (ie. optimise too aggressively or naively), it will sometimes be to the detriment of all the KPIs as the optimisation will be pushing too strongly in one direction (perhaps it is outside the parameter space for which it was originally tuned, or perhaps it pushes the metaheuristic into search-space regions which are more difficult to escape from). This is most acutely seen in Region 2 when using the high cost per hour value. Conversely if you drop the cost per hour to a low value, the (very modest) reduction you get in distance is very badly paid for in terms of much longer durations. What is most likely happening in this case is that the routes are including much more waiting time (waiting at delivery points for the time windows to “open”), in order to avoid even a short trip (incurring distance) to a nearby delivery point that could be done instead of waiting.

The problem of striking the right balance is most acute with metaheuristics which can only really be tuned and investigated by being run many times across multiple data sets, in order to get a feel for how the solution “cost curve” looks in response to different input weightings. In our example, an in-between value for cost per hour seems to strike the best balance to produce the overall most desirable KPI outcome.

The Launch of Biarri’s WorkBench

/0 Comments/in , , , /by

With the impending launch of Biarri’s workbench and our ongoing close relationship with Schweppes for the daily routing of soft drink deliveries (an application of perhaps the most well known operations research problem: the vehicle routing problem), I thought that the following excerpt from a journal article submitted to the Asia Pacific Journal of Operations Research would be a very timely blog post.

The journal article is entitled “Real-Life Vehicle Routing with Time Windows for Visual Attractiveness and Operational Robustness” and it describes the vehicle routing algorithm we have implemented for Schweppes.

The excerpt details a specific example encompassing two things we are very passionate about at Biarri. First “Commercial Mathematics” – that is making OR (well not strictly just OR) work in the real world. And second, the revolutionary capabilities that the advent of cloud computing has for the delivery of software.

“Vehicle routing problems manifest in a remarkably wide range of commercial and non-commercial enterprises. From: industrial waste collection to grocery delivery; underground mining crew replenishment to postal and courier collection and delivery; inbound manufacturing component transportation to finished car distribution; in-home primary health care delivery to pathology specimen clearances from surgeries for analysis; and from coal seam gas field equipment maintenance to beverage distribution, to name but a few.

Automated planning systems used by industry at present are predominantly client-server or desktop based applications. Such systems are often: expensive, requiring a large upfront capital investment; accompanied by a large software deployment project requiring initial and ongoing IT department cooperation; customisable to a particular organisations requirements, however commonly retain a large amount of exposed functionality due to the breadth of the existing client base; and require substantial user training as the workflow is usually not restricted in a linear fashion …. Each of these characteristics constitutes a barrier to adoption of automated planning systems, and for most small to medium enterprises these barriers prove insurmountable.

With the advent of cloud computing and software as a service (SaaS) these barriers are being removed. SaaS: embodies a different commercial model; has essentially no IT footprint; mandates (as vendors may never directly interact with potential clients) simple intuitive linear workflows; and involves almost no end user training beyond perhaps an optional demonstration video.

The emergence of this new avenue for the delivery of optimisation based planning systems heralds, a heretofore, unparalleled opportunity for operations research practitioners to engage with a wider potential consumer base than ever before. However, the nature of the delivery mechanism requires the algorithms developed: to be robust and flexible (within their domain of application they must be capable to dealing with a wide range of input data); to have very short run times (the user base is more likely to be under time pressure than ever before); to produce high quality solutions (noting the inherent trade off between run time and solution quality); to be wrapped in a simple linear workflow (meaning it is always obvious what the next step in the planning process is); but above all, be able to produce real-life, practically implementable solutions, without the need for user training and/or experience.

For pure delivery, or pure pick up vehicle routing applications, real-life, practically implementable solutions are often synonymous with geographically compact, non-overlapping routes with little or no intra-route cross over. There are numerous reasons why such solutions are preferred …. If a customer cannot be serviced at the preferred time (e.g. the vehicle cannot get access, the customer is closed, another delivery is taking place, the customer is too busy), because the route stays in the same geographical area, it is easy to return to the customer at a later time. During busy traffic periods drivers are loathe to exit and re-enter a motorway to service individual customers. Even though such customers may be enroute to the
bulk of the customers the route services, thus incurring a minimum of additional kilometres, they may nevertheless be far from the majority of the customers the route services. If there is severe traffic disruption, it is easier to use local alternate routes between customers in a route that is geographically compact to ensure that pick-ups or deliveries can still be made. Third party transport providers, which prefer routes to be as simple as possible, may exert some influence over the planning process. Finally … it is easier to maintain customer relationships by assigning drivers to routes that routinely service a similar geographical area. In summary, solutions which are more visually attractive are more robust, and thus more likely to actually deliver the full extent of the cost savings that should flow from the use of automated planning systems.

This paper describes an algorithm for the vehicle routing problem with time windows, …. The algorithm is: robust and flexible; fast; wrapped in a user interface utilising a simple linear workflow and so requires no user training or experience; and produces high quality, visually attractive and practically implementable solutions.”