Route Optimization for Mixed Fleets

With the introduction of cargo bikes, light electric vehicles, vans, and so on, dealing with a variety of complementary means of transport has become a common logistical problem. How do you determine the most appropriate routes when the characteristics and operational costs of vehicles can be so radically different?

Our route optimization API now closely models all these various costs. As always, we rely on the most recent version of VROOM, the open-source software that we have developed.

Different Vehicles, Different Costs (image by Freepik).

Mixed Fleets

Our multi-profile optimization capabilities have long been able to factor in the way route times vary depending on vehicle type, but that is just one part of overall costs. Every vehicle has a specific per-hour cost, and their fixed costs can vary widely, too, for example if these are rental vehicles, or those of sub-contractors, etc.

Our API now takes into account not only fixed costs, but hourly vehicle costs as well. The goal is no longer simply to optimize overall travel time, but rather to determine the real operational cost of routes. As a result, in addition to assigning tasks and sequencing them, we can now optimize the vehicular resources to be drawn upon in terms of overall cost.

Vehicle Range

In the field, vehicle range is an essential consideration, regardless of whether limiting factors are material in nature, such as battery-life, or a matter of operational choices. For example, it is important to be able to manage the physical effort required by routes that are serviced by bicycle.

Simply putting limits on work time is much too rigid an approach and the solutions it provides are significantly less than optimal. That is why, along with time windows, we have developed a way of limiting the travel times of individual vehicles. Our algorithms will not allow a vehicle to go beyond its maximum range, yet our models still offer maximum flexibility and thus still provide the best solutions.

Computing Times

Implementing these new features necessarily increases computing times. Because we remain dedicated to providing solutions as quickly as possible, we have tailored our algorithms to minimize that added time. Actually, the recent improvements that we have made in accelerating problem solving already compensate for the additional time these new features demand.

Contact us if you would like to optimize the way you manage your fleet!

Solving Problems Better and Faster

We continually work to improve the algorithms of our API for route optimization so that we can provide quality solutions with enhanced efficiency. The matter at hand: the speed with which we interact with business-specific tools and the ability to rapidly solve problems of increasing size. Let’s have a look under the hood of the most recent version of VROOM, the open source software that we have developed.

Ever Better, Ever Faster

The above graph depicts, for 56 problems, the improvement in solution finding that was achieved through various trade-offs between solution quality and calculation times based on the Solomon benchmark, which is one of the standards in the field. The smallest gap to optimal solution costs, which on the average was already at a very low 1.81%, has now been further lowered to 1.63%. Not an easy task, given that the calculation time has been nearly halved: on the average, barely 360 milliseconds for problems that each involve 100 delivery points.

In the field, we noted that calculation times for the problems of one of our clients were reduced by 42%.

Improved Solutions

The combinatorial complexity of vehicle routing problems is so great as to make an exhaustive search for optimal solutions unrealistic. That is why we have adopted a local search strategy that allows us to limit our focus. The search process has to be at once sufficiently thorough to generate the best solutions and limited enough to maintain ultrafast calculation times. A newly added local search operator now allows us to reach even better solutions, and which are experienced as such in the field, for vehicles travel through neighboring locations far less frequently.

Setting Records for Problem Solving Speeds

To sharply reduce local search calculation times, we cut off some of the “branches” at the outset. Calculating and storing previously untapped data allows us to identify more quickly these inoperable solutions that fail to respect time and/or capacity constraints, and even constraints that are not necessarily explicit, such as the maximum number of jobs a given vehicle can perform, which may be limited by other constraints. The end result yields solutions in as little as half the time without having unduly limited the search for valid solutions and thereby overall quality.

Contact us if you would like to measure the impact of these improvements on your use-case.

New features For Our Route Optimization API

We are constantly working to improve our API and provide our clients with the best possible vehicle routes for their business. Zero in on our most recent reworking that draws on a new version of VROOM, the open-source software that we have developed for optimizing fleet operations.

The operational effectiveness of itineraries depends on the precision of the models developed for service times and the balance of workload distribution that proposed solutions offer. – Map data © OpenStreetMap contributors

ENHANCED MODELS FOR PROBLEM SOLVING

Workload Management

Achieving efficient cost-reducing routes is sometimes not enough from a practical perspective, as shown above (left). To adhere to a plan of operation while maintaining a balanced distribution of work involves avoiding discrepancies in workloads (right).

Until now, we have limited loads by using a default figure for maximum capacity. It is now possible to enter the maximum number of jobs each vehicle can handle. Not only does this new approach work for all kinds of tasks, but it also cuts calculation times in half while continuing to respect the usual time constraints in the field.

Modeling of Service Times

Frequently, several jobs are carried out at the same location, as when deliveries are made to several residents in an apartment building or when pick-ups for different clients are made at a store. In this instance, some of the time spent at this location is the same for several jobs and cannot be calculated in each instance as service time. With this in mind, we have introduced the notion of a setup period to model the time it takes to park and arrive at the site. The service times for the individual jobs carried out remain cumulative, as before, but the setup period for that one location is counted only once.

Making Use of Existing Schedules

It doesn’t always make sense to start from scratch when problem solving, such as making marginal changes to an existing schedule or simply testing the feasibility of adding jobs. This is especially the case for appointments made online that have to be confirmed (or denied) quickly. For problems of this kind, it is now possible for clients to provide an existing schedule for optimization as the initial step in the high-speed solution-finding process.

Improving Problem Solving

Conceiving and improving approaches for optimization lie at the heart of our expertise. In addition to the functionalities we have added, we have also brought into play a new local search neighborhood, a version of Thibaut Vidal’s SWAP* operator that appeared in a recent article and that we have adapted for our purposes to manage an even greater number of constraints, time constraints in particular. For some reference benchmarks, the average gap to optimal solutions has been reduced from an already low +1.73% to +1.32%, which, given our impressive calculation times, is quite significant.

Contact us if you would like to try out these additions and improvements to our API for route optimization.

Socleo Optimizes Local Food Distribution Networks

Thanks to the incorporation of our API for route optimization, Socleo, the specialist in local food distribution networks, can now offer its clients this added feature while they continue to use the software they are familiar with.

socleo + verso

A Specialist in Local Food Distribution Networks

Designed for growers, processors, and distributors, Socleo’s multi-faceted software can be adapted to individuals, communities, or regions. It can be used for sales, by offering an on-line store and a showcase website, for logistics, by overseeing inventory and deliveries, and for administrative matters, by generating invoices. It is a complete management platform, wholly adapted to the needs of local food distribution networks.

A Collaboration that Benefits the People Directly Involved

With the incorporation of our API, Socleo has given its clients access to optimized routing. And it has done so without requiring them to move on from the software they are accustomed to, which already includes most of the specifics needed to configure problems in view of route optimization.

This new addition gives those involved in local food distribution greater logistical control in two ways: first, by handling a large part of their scheduling automatically; second, by reducing delivery times and thereby reducing the impact on the environment, in harmony with the spirit of local food distribution networks.

Contact us if you, too, would like to incorporate route optimization into your management software.

Multi-Profile Optimization

For a mixed fleet, the efficient use of different vehicle types is crucial in determining the logistics of the last-mile. And this is precisely the efficiency our API can now provide thanks to an updated version of VROOM, the open-source software that we have developed for optimizing fleet operations.


An example of the way tasks are normally divided between cars and electric bikes – Map data © OpenStreetMap contributors

Handling multiple profiles

A vehicle’s “profile” provides its characteristics and dictates the routes it can take and the speed at which it can negotiate each leg of them. For route optimization, it is essential to be able to calculate the differing speeds of electric cargo bikes, lightweight vehicles, and trucks.

To date, our API has proposed a variety of vehicle profiles, but one particular vehicle has always been chosen to fit the scale of a given problem. In other words, until now, it has not been possible to optimize routes that are most efficiently served by vehicles of varying kinds. This was a significant limitation, for it is often necessary to combine vehicle types. And the need for a combined approach continues to increase. For example, for environmental reasons, certain urban areas are now open to green transport only.

Our API can now take these restrictions into account and select the vehicle best suited for each context. In the illustration above, five electric bikes are used for the short hauls in heavily trafficked, urban areas, while cars are used for the longer runs outside the city. Our API’s ability to adapt to different vehicle profiles comes in addition to its longstanding ability to take into account other factors, such as load capacity and availability.

Efficient Implementation

Modifying the way we deal with route times was a delicate matter, for it involved a primitive that lies at the heart of all our optimization algorithms. On a technical level, we had to refactor our code. This gave us the opportunity to include a speed coefficient, which allows our users to fine-tune even more accurately the transportation times of each vehicle.

To take the diversity of vehicles into account, we also had to adjust our approach to problem solving. Then, because this added feature provided solutions for new kinds of problems, we had to introduce new performance benchmarks. The solutions proved excellent, both in cost-effectiveness and for the speed at which we arrived at them, the latter because of the optimized data structures we put in place.

Contact us if you would like to discuss the best way to manage your mixed fleet of vehicles.

DeliverMe.City’s Innovative Approach to Last Mile Delivery

DeliverMe.City allows users to determine exactly when and where they want their packages delivered directly to them. The company, which Challenges listed as one of the most innovative and promising of 2021, is highly attuned to social and environmental issues. The flexibility it has added to the final minutes of deliveries draws heavily on our API for route optimization.

The Uniqueness of DeliverMe.City

As opposed to many platforms, DeliverMe.City has chosen to work with salaried deliverymen. Beyond its social dimension, this approach effectively makes its deliverymen representatives of the service they provide, thereby ensuring its quality.

To reduce its impact on the environment, and noise levels as well, deliveries are made on power-assisted bicycles, and electric-powered vehicles are used exclusively throughout the process of procuring supplies. The concern for technical reliability and quality led the company to work with a French designer of cargo bikes.

Above all, DeliverMe.City has placed its clients at the heart of its service by allowing them to determine the place and time of deliveries, and even the possibility of altering time and/or place while goods are already on their way. This flexibility means that clients are dictating scheduling rather than being dictated to by logistics. It is an approach that represented a major challenge in terms of optimization.

Organization and Modelization

Increasing the number of factors to be taken into account and allowing for possible adjustments can naturally lead to added operational costs. For such an approach to be sustainable requires an ad hoc organizational system. To this end, DeliverMe.City conceived a multi-layered delivery process made responsive and flexible by synchronizing the work of its various participants.

Turning DeliverMe.City’s vision into reality was a challenge for our expertise in optimization that proved a highly enriching experience. The modelization of the problem that we worked together to construct allowed us to structure successfully the in-the-field organization.

Thanks to our API for route optimization, the company’s scheduling can be continually updated from the time orders are accepted through the period when they are on the way. We sincerely hope that DeliverMe.City will meet with the success its innovative spirit deserves.

Don’t hesitate to contact us should you, too, have a challenging problem in optimization.

A New Scheduling Feature

The solve feature of our API assigns operations at pre-determined locations to various routes by establishing the most cost-effective order in which to perform them. Plan is a new, complementary feature designed to provide users with information invaluable in making adjustments to their scheduling.

Oh dear! Oh dear! I shall be late! (Alice’s Adventures in Wonderland, Chapter 1) – Photo by Veri Ivanova on Unsplash

Information for Decision Making

In responding to unspecified needs or contingencies, schedulers can marginally adjust optimal route schedules in the field. They make their adjustments through their expertise in balancing the cost and quality of service with various scheduling constraints, most notably time constraints.

The new plan feature allows users to update the ETA of any route while taking into account operational costs and the impact of any changes. For every change, it provides users with pertinent information: the number of delayed jobs, the length of delays, the degree to which time constraints and the theoretical load capacities of vehicles have been exceeded, differences in cost, etc. By providing users with specific information, plan allows them to apply their expertise more proficiently.

A Problem that Appears Simple… on the Surface

When a schedule is overbooked, it is impossible to respect all the time constraints. Is the best solution to leave at the originally scheduled time and be late for certain jobs? If so, our API can determine the length of delays. But it can also propose an earlier starting time, in so far as constraints in the field allow, and thereby reduce delays and lessen the perceived decline in the quality of service.

Or consider the example of a scheduler who wants to move a delivery originally planned for the afternoon to the very first one on the route. Doing so would change the delivery time of every subsequent job. In such a case, our API recognizes that the time of this delivery alone should be altered and proposes moving the starting time up early enough to avoid delays further down the line.

Optimization under the Hood

By making the usual time constraints flexible, the plan feature allows for scheduling changes while minimizing their impact, which is its principal optimization objective. And it also keeps makespans to a minimum while scheduling tasks as early as possible.

The linear programming approach that we have implemented not only guarantees optimal solutions, but it avoids the frequent pitfalls of unreasonably long calculation times. With our cutting-edge ad-hoc modelization, the response-time of our API is so fast that users can take advantage of it in real time.

Contact us to learn more about what this new feature might mean for you.

Taking Breaks into Account

Determining cost-effective routes requires us to take into account the needs drivers experience on the road, in particular their need to take breaks. Thanks to a new version of VROOM, the open-source software we have developed for optimizing itineraries, this functionality that our clients have been impatiently awaiting is now available through our API.

Time for a break – Photo by Phil Garrison on Unsplash

Flexibility of Time and Location

Up until now we were able to define a break as one of a driver’s several tasks, but that meant pre-determining the location at which the break was to be taken. At times this approach worked well, but as a rule the site of the break depends on the optimized route. With our new approach we can now define breaks as tasks without pre-establishing their location.

Even pre-determining the time of a break can have a negative effect on optimization. It would clearly be foolish to cancel a job simply because performing it would mean that the driver’s break would have to begin at 12:03 rather than at 12 noon sharp, as planned. Moreover, we have to be able to ensure that breaks are taken early enough to allow drivers to meet subsequent deadlines. Our API provides this flexibility, guaranteeing breaks of adequate length that comply with in-the-field needs.

To take an even more complex example, imagine a situation in which the final morning job ends before the midday break can reasonably begin. No one wishes to waste time waiting, and putting off the break could cause delays for jobs that follow. We are now capable of splitting travel time before and after breaks, thus minimizing downtime and providing pertinent solutions even when time constraints are especially tight.

Increased Functionality with the Same High Degree of Performance

The newly developed ability to include several breaks in itineraries makes it possible for us to model a great number of new situations. For example, planning work that stretches over several days and involves rest times at night is trivial.

The good news is that we have been able to add this functionality without significantly increasing algorithmic complexity. In a word, whether taking breaks into account or not, our API continues to provide elegant solutions at the same record speeds as always.

If you would like to try out this new functionality, contact us to get your API key.

Teliae integrates Verso’s API into its Software

Teliae specializes in developing business software for logistics management and the transport industry. Its Transport Management Systems (TMS) are used by more than 450 carriers of all sizes: Ciblex, XPO, Kuehne Nagel Road, Michelin, Groupe Mazet, GFS, Office Depot, DGS, Normatrans, Noyon, and others. To increase the advantages of the solutions it provides, Teliae has integrated Verso’s API for route optimization into its software, which will save its clients time spent scheduling and reduce operational costs.

Teliway in action – Map data © OpenStreetMap contributor

The Keys to a Successfully Integrated Tool

Users of the Teliway TMS will now be able to access functionalities for the optimization of fleet operations with just one click. No need for additional tools or to reconfigure data; users of the software will continue to work within familiar confines. Access to these functionalities is immediate, just one simple step in the ergonomic operational process that the Teliway software provides.

The success of an integrated tool for route optimization depends largely on its ability to consider each and every one of a client’s needs so as to generate pertinent solutions in the field. To reap the greatest benefits from VERSO’s API, Teliae has inputted its clients’ specific constraints: routes based on predetermined but adaptable sectoring, constraints imposed by loading dock workflow, task priorities, schedules and working hours, and so on.

“I’m just blown away by the speed of these calculations”

Jérôme Petit, Teliae’s Director of Operation

Thanks to the speed with which calculations are performed the optimization module can be used in real time and help generate more enlightened business decisions. The user, obviously, given his expertise, still has the final word and can make adjustments through either the software’s presentation of the fleet schedule or a cartographic view of it.

The Key Word is Complementarity

“I’m just blown away by the speed of these calculations,” Jérôme Petit, Teliae’s Director of Operations, said after watching VERSO perform. That is precisely what we seek to do: focus on a “software building block” that can solve specific problems with blinding efficiency. We are delighted that Teliae has placed its trust in our highly specialized expertise in optimization, and we know that Teliae’s long and rich experience in the field will make our collaboration a success sure to benefit its clients.

Contact us if, like Teliae, you would like to optimize your clients’ route planning and further enhance the performance of your software.

Managing Pickups and Deliveries

Verso’s API for route optimization has just been enhanced. We can now model pickups and deliveries in combination, which allows us to deal with a greater variety of situations. As always, the latest update is based on a new version of VROOM, the open-source software we work with to optimize itineraries.

Photo by RoseBox

A New Feature

The previous update allowed us to deal with objects that all had to be either loaded when the vehicle set out or brought back at the end of a round. In the trade, pickup and delivery is the phrase used to designate an object picked up and later delivered in the course of the same round. The newly added modeling entityshipment deals with this exact situation.

And all kinds of combinations are possible, for shipment objects can be combined with the previously managed job objects of single deliveries or pickups.

New Uses

It is now possible to optimize the deliveries and pickups of multiple clients to or from a variety of storage areas (warehouses, stores, etc.), all while taking into account the usual factors: priorities, load capacities, schedules, expertise in handling, and so on. When dealing with a multi-site fleet of vehicles, the optimization tool minimizes operating costs by determining the vehicles best suited for a series of pickups and its associated deliveries.

The new feature can also be applied to the transport of people, with possibilities for optimization combined with innovative solutions for carpooling or the use of common-carrier vehicles. In the case of individual requests for transportation, calculation time is so short that schedules can be updated and optimized in real time.

The Same Excellent Results as Always

As has consistently been the case, the results we achieve are both verifiable and reproducible. According to the well-established benchmark Li & Lim 100, our approach obtains absolute optimal results more than 46% of the time, for an average of just 1.22% over optimal cost. And everything is done in record time, with problems involving a hundred different locations solved on average in 256 milliseconds.

If you are interested in trying out this new functionality, contact us for an API key.