По русски

Information on VrpPd

Main features of VrpPd software

VrpPd can solve near to optimality different CVRP,VRP,VRPPD,dial-a-ride tasks with or without time windows. It plans routes so, that it can minimize visits to clients ,if possible (or can not to do this), plans routes with multiple trips for loading/unloading if nessesary, can plan routes in LIFO or FIFO loading mode and respects transport job for vehicle to transfer cargo - this provide additional saving.

A great influence on this program development was provided by the next works :

VrpPd is very easy to install and use - simply copy the two files in any folder on your Windows PC with Microsoft.Net framework v.4.5.2 or higher (virtually any PC), processor - at least Intel with SSE4.2 support or better. All data are stored in MS Access database, so you don't need support for large databases, and it easy to integrate with other software. It has built in features to import information from tab-delimited text files and has support for Google Maps.

VrpPd uses as many processor cores as possible - and works faster , it is important if you work with large tasks.

You can download test version at the bottom of this page.

Description of VrpPd

VrpPd is software for solving capacitated vehicle routing problem with simultaneous pickup and delivery and time windows. This is generalization of vehicle routing problem.- A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations. So, at example ,if pickup location is the same for all orders and is at vehicles depot - we have a classic CVRP problem,with the the exception, that solver will automatically plan several tours for vehicle, if it is nessesary. Latest version also supports multiple depots mode and "open chain" mode - when vehicle need not return to the depot.

With VrpPd program you can optimize vehicle routes,at example, to deliver cargo from several locations to number of customers and simultaneously transfer some goods between customers.You define distances and times between points,parameters of your vehicles and list of orders - commands to transfer cargo from some point to other.You can set parameters of vehicles to obtain more balanced routes and respect vehicle capacity.

So you can more clearly imagine such a problem, look at the picture below.

Example of VrpPd problem

Distances you define the same way as in VrpCalc,then you define a fleet of heterogeneous vehicles :

VrpPd - Vehicles

For every vehicle you define it load capacity,maximum allowed run and additionaly you can restrict number of orders per route - this is critical if load/unload operations take a lot of time.Your also define starting point for every vehicle and set attribute "Tour" if vehicle needs to return to starting point.You also define start time and end time for every vehicle and possible load restrictions none,LIFO (last in first out manner - i.e. goods have to be delivered in the reverse order they were picked up) or FIFO. You also can define list of "Skills" for every vehicle.(For each order you can defile list of required "Skills"). This is required, if you need that some orders to perform with certain vehicles).

Then you define list of orders:

VrpPd - List of orders

You give the software certain time to perform optimization using specific algorithm (LNS with simulated annealing) and press stop:

VrpPd - Solving

Program optimizes time or mileage for all vehicles to carry out all given orders, taking into account vehicle restrictions. If some vehicle turns out to be unnecessary - the planned route for it will be displayed as zero.

Solution found - results(route for each vehicle with load/unload orders) are copied into text file. (You can also view solution right during optimization by double clicking on a corresponding row in window). Here is solution VRPPD examples in different modes : example 1,example 2,example 3


One of the unique features of VrpPd is possibility to optimize not only distance but also amount of transport job (picture to the right illustrates this with a simple example). We have depot D and two customers "A" and "B". One vehicle must deliver to them 30 and 100 units of cargo, respectively, and return to the depot. Distances are shown on the picture. If we plan route "D->A->B->D" or "D->B->A->D" - the route will be of the same length: 110. If we plan route "D->A->B->D", the vehicle will carry 100 units of cargo for "B" for distance 80, and 30 units of cargo for "A" for 50. However, if we plan route "D->B->A->D" we will carry 100 units of cargo for "B" for only 30 and for "A" - 60. Thus, though no different in overall route, there is significant difference in the distance for transferring heavier cargo.

Even more strange is the situation if you plan a route "D->A->B->D" to transport passengers traveling to "A" and "B". Passengers traveling to "B" will be very surprised that instead of 30 they traveled 80.

Majority of available software does not recognize the issue. VrpPd has been designed to plan route accordingly, providing additional fuel economy and making more logical routes.



To test program, I also solved A-n80-k10 and G-n262-k25 instances of CVRP problem.CVRP is partial case of VRPPD when all orders are to deliver goods from depot to every client.


I also test VrpPd support for time windows. There are separate time windows for loading and unloading operations, and for each individual vehicle. The optimization can be carried out both by distance and time of use of vehicles, of course, taking into account time windows and other constraints. To test time-windows mode, I have solved some well-known CVRPTW instances - you can take a look at example of results here



 DISCLAIMER OF WARRANTY AND LIABILITY
 THE SOFTWARE AND THE ACCOMPANYING FILES ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. 
 TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, AUTHOR DISCLAIMS ALL WARRANTIES, EXPRESSED OR IMPLIED, 
 INCLUDING, BUT NOT LIMITED TO, ANY IMPLIED WARRANTIES OF PERFORMANCE, MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, 
 AND NONINFRINGEMENT.TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY 
 DIRECT, INDIRECT, CONSEQUENTIAL OR INCIDENTAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
 DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS INTERRUPTION OR LOSS OF BUSINESS INFORMATION) ARISING 
 OUT OF THE USE OF OR INABILITY TO USE THE SOFTWARE.

Here you can download program VrpPd 2.0.3.9. Simply unpack downloaded vrppd2_x86.zip in some directory on your disk. It contains three files : VrpPd.exe.config - with typical options, program itself - VrpPd.exe and VrpPd.mdb (contains test data,for easy program testing - Solomon r105 CVRPTW instance - if you do not need it, delete this file, program will create new, empty). If you have 64bit OS and 64 bit Microsoft.ACE.OLEDB.12.0 provider installed, you can download VrpPd for any cpu - it works bit faster.(Of course, if you want to solve such tasks, it is better to use 64 bit version and powerful multicore computer.) In unregistered version some Google map functions are disabled and you can only view results and can not save or print it. Registered version can also work in "silent" mode - you start program with one additional parameter - "Number of iterations" - program silently performs this number of cycles of simulated annealing, creates solution files, and exits.

Registration is free for educational institutions.(Official email letter is required).

Here is some documentation for the program.


© 2014-2017 If you need more information on VrpPd,or are interested in solving similar tasks - contact me by email shobb@narod.ru