wiki:BluePrint/VehicleRouting

Version 26 (modified by Fran Boon, 10 years ago) ( diff )

--

BluePrint: Vehicle Routing

Table of Contents

  1. Introduction
  2. Stakeholders
  3. User Stories
  4. Requirements
    1. Functional
    2. Non-functional
    3. Interoperability
    4. Standards
    5. System Constraints
  5. Design
    1. Data Model
    2. Workflows
    3. Site Map
    4. Wireframes
    5. Technologies
  6. Current Implementation
  7. Planned Implementation
  8. Future Extensions
  9. Outstanding Questions
  10. References

Introduction

Vehicle Routing tries to determine possible (optimal) routes for the transportation of resources from warehouses to facilities.

Problem class definitions:

Stakeholders

Users

  • Supplier (Warehouse) (includes Warehouse Manager, Fleet Manager, Finance Officer)
  • Shelter (includes Volunteers at Shelter)
  • Transport Staffers (Driver)

Who are affected?

  • Sahana Developers - Few of the models, should be tweaked
  • Warehouse - Extra information to be provided about capacity of vehicles
  • Transport Staffers - Additional communication about routes to be taken
  • Volunteers at Shelter - Additional data, about arrival time(s) of resources

User Stories

  • Supplier can determine which items will be delivered by which vehicle (in order to load the vehicles accordingly)
  • Supplier can determine a possible (efficient) route for each vehicle to deliver the requested items
  • Supplier can determine the costs/time for the delivery
  • Requester can be given an estimated time of arrival of the requested items
  • Driver receives the route for the delivery

Requirements

<Group requirements in subsections, e.g. etc.> <​http://en.wikipedia.org/wiki/Requirements_analysis requirements> <Identify different types of requirements:>

Functional

Non-functional

​http://en.wikipedia.org/wiki/Non-functional_requirements

Interoperability

Standards

System Constraints

Design

<Where relevant include alternative design options>

Data Model

(e.g. EER or class diagrams)

Workflows

  1. Request for resources, has come into the database (some generic request, by anyone)
  2. Warehouse manager, gets the details of the shelters and resources to supply
  3. Fleet Manager, supplies to the warehouse, with vehicles
  4. VRP Module is run upon
  5. This gives the following output
    • Route for each vehicle
    • Cost per vehicle
    • Resources in each vehicle
    • Time to reach shelter, by each Vehicle
  6. Cost per vehicle, is given to Finance Officer, for approval
  7. Route and Cost per vehicle, is given to each Driver
  8. Time to reach shelter, by each Vehicle, is given to respective Volunteers
  9. Journey begins

Site Map

<for User Interface solutions>

Wireframes

<for User Interface solutions>

Technologies

Current Implementation

This implementation is entirely based on the examples provided by OptaPlanner: ​https://github.com/droolsjbpm/optaplanner/tree/master/optaplanner-examples/src/main/java/org/optaplanner/examples/vehiclerouting

The main method of this module is present at: ​https://github.com/wolfshadow18/Vehicle-Routing-Problem/blob/master/Sahana-Final/Sahana/examples/sources/src/main/java/org/optaplanner/examples/vehiclerouting/app/VehicleRoutingApp.java

This main method takes an argument, which is a path for an unsolved Capacitated Vehicle Routing Problem, which is in the form of a XML file.

An example of an unsolved XML file, can be seen here - examples/data/vehiclerouting This unsolved XML file has following main attributes:

  • Location List (Longitude and Latitude)
  • Depot List (With a reference to a Location in the Location List)
  • Vehicle List (Stating the Capacity and the location of the Vehicle)
  • Customer List (Stating the Demand of each of the locations)

When such a XML file, is passed to the module, it returns back, a Solved XML file, which is stored in the same directory as the unsolved file, which was passed earlier, with the prefix – “solved-” This XML file, has to be parsed by the modules in Sahana, and should be utilised upon. The final Solved file, diagrammatically, looks similar to this. This Solved file, tells which Vehicle should go to which Location(s), in which order. Such an example, can be seen here: ​https://github.com/wolfshadow18/Vehicle-Routing-Problem/blob/master/Sahana-Final/Sahana/examples/data/vehiclerouting/solved-cvrp-72customers.xml

https://raw.githubusercontent.com/wolfshadow18/Vehicle-Routing-Problem/master/Solved%20Example.png

To Test the module, please perform the following steps.

  • Download a copy of the module, which is currently being hosted at, ​https://github.com/wolfshadow18/Vehicle-Routing-Problem/
  • Download IntelliJ Idea/ Netbeans. It is recommended to use the former.
  • Open pom.xml, which is located at examples/sources/ from the IDE
  • While setting up for the first time, it may take some time, as it needs to download its Maven dependencies.
  • After which, set up a Run configuration, for this project. Please look at the image below. The program arguments, should ideally contain the path of the unsolved file, that you wish to pass to the module.

https://raw.githubusercontent.com/wolfshadow18/Vehicle-Routing-Problem/master/Run%20Configuration.png

  • Go to Sahana/examples/sources/src/main/java/org/optaplanner/examples/vehiclerouting/app/VehicleRoutingApp.java, and run the project.
  • Troubleshooting: In case, an error such as- “The working directory should be set to the directory that contains the data directory (which is not the data directory itself) “ pops up, please check whether your working directory is the same as mentioned above.
  • You would notice that, in the console, the program has started running, typically, for testing purposes; the running time of the module has been limited to 1 minute. However, this can be increased, by changing, /examples/sources/src/main/resources/org/optaplanner/examples/vehiclerouting/solver/vehicleRoutingSolverConfig.xml
  • In this file, find the attribute minutesTimeSpent, and change it to a positive integer. This can be done whenever necessary as all the attributes of this file, have methods in which they can be accessed.

Few points to be noted:

  • As solving time of the problem is increased, more efficient results can be obtained.
  • The file is returned back to the user using the function, getOutputFile(), which is also present in VehicleRoutingApp

Planned Implementation

Given

  • A transportation network
  • A single supplier, having a fleet of vehicles of given capacities, and a warehouse of goods
  • A set of demands (who, what, when)

Assumptions

  • All routes in the transportation network, are accessible
  • Sufficient vehicles
  • Sufficient drivers
  • Sufficient fuel
  • Vehicles transport all the fuel they need for transport
  • Minimizing total distance also minimizes delivery time

Goal

  • Satisfy all demands within their time windows
  • Minimize total distance

Future Extensions

  • Multiple Warehouses
  • Minimize fuel consumption
  • Maximize the number of demands satisfied
  • Handle routes that suddenly become unavailable
  • Re-optimization of plan if routes become available again, without sending vehicles home
  • Handle different types of routes
  • Handle case of too few vehicles to transport all in one shot
  • Low fuel at start
  • Low fuel availability within the network to refuel vehicle
  • Handle time for loading/unloading
  • Handle breakdowns of vehicles
  • New demands coming in over time
  • Assignment of drivers to vehicles

Outstanding Questions

<Questions about the features or design that haven't been (and need to be) answered>

References

BluePrint

Note: See TracWiki for help on using the wiki.