In our constantly evolving drive to provide optimal route planning, the introduction of electric vehicles has required us to take new factors into account. To this end, we have updated our API with new features that we added to VROOM, our open-source solving engine for vehicle routing problems.

Vehicle Range

We had already taken a first step towards modeling vehicle autonomy by making it possible to limit the overall road time for individual vehicles. But frequently, the distance traveled is as, if not more, limiting than travel time. We needed to include distance constraints, for example for electric vehicles or couriers on bikes. To that end, we introduced a max_distance parameter applicable to individual vehicles to ensure that itineraries take into account the key factors in a vehicle’s autonomy: travel time and/or travel distance.

A More Realistic Modeling for Costs

To include vehicle and driver travel time in calculating costs, our previous update introduced the notion of “hourly cost”. But travel distance has a significant impact on cost, too, and it can vary widely, depending on the price of gas or diesel or, for electric vehicles, recharging batteries. Our model for route optimization now factors in cost per km per individual vehicle.

We are no longer simply looking to reduce travel time. Optimization now takes into account the overall costs associated with vehicles, be they fixed costs or costs dependent on travel time or distance.

Contact us if you would like to use advanced cost modeling as you optimize route planning for your fleet of vehicles.

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.

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!

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.

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.

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.

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.

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.

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.

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.

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.

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.