Skip to content

Latest commit

 

History

History
145 lines (113 loc) · 6.13 KB

Home.md

File metadata and controls

145 lines (113 loc) · 6.13 KB
Raw

About Optimizer API

Optimizer API provide a service to adress Rich Vehicle Routing Problems. At this purpose it can call multiple tools or method to provide a solution with the provided constraints. Moreover, some pretreatments, also called interpreters can be applied in order to complete the problem or split it.

Capabilities

Using the denomination used by Caceres-Cruz & al the supported constraints are the following :

Restriction Code/Id
Multiproducts CP
Vehicle Capacity C
Homogeneous Fleet of Vehicles FO
Heterogeneous Fleet of Vehicles FE
Fixed Fleet of Vehicles VF
Fixed Cost pet Vehicles FC
Variable Cost of Vehicles VC
Vehicle Site Dependance DS
Vehicle Road Dependence (router side) DR
Duration Constraints/Length L
Driver Shifts/Workind Regulations (partially) D
Balanced Routes (partially) BR
Symmetric Cost Matrix CS
Asymmetric Cost Matrix CA
Intraroute Replenishments IR
Time Windows TW
Multiple Time Windows MW
Pickup & Delivery PD
Simultaneous Pickup & Delivery PS
Multiple Visits MV
Multiperiod/Periodic MP
Multidepot MD
Different End Locations/Open Routes O
Different Start and End Locations DA
Departure from Different Locations DD
Precedence Constraints PC

& more...

Data Model

The data model is constructed around a main object called vrp and is constituted of multiple high level entities

{
  "vrp": {
    "points": [],
    "vehicles": [],
    "units": [],
    "services": [],
    "shipments": [],
    "matrices": [],
    "rests": [],
    "relations": [],
    "zones": [],
    "configuration": {}
  }
}

Those high level entities are completed by few others as Timewindows and Activities which are locally defined. To define the model, the first step will be to describe every Point which will be used in the description of the problem. This will include the depots and the customers locations. Furthermore at least one Vehicle is mandatory and define at least one Service or Shipment will be essential to launch the solve. The others entities are optional but may be mandatory regarding the problem to be adressed.

Interfaced tools

OR-Tools

Google Optimization Tools (a.k.a., OR-Tools) is an open-source, fast and portable software suite for solving combinatorial optimization problems.

A wrapper has been developed to allow the call of the expected model and constraints : Optimizer-Ortools

VROOM

VROOM is an open-source optimization engine written in C++14 that aim at providing good solutions to various real-life vehicle routing problems within a small computing time.

VROOM provide a direct exchange format in JSON

Resolution

The resolution is divided in three main steps. The first one Define main process isolate the independent resolutions requested through the parameters several_solutions and repetition.

Define process allows to manage the recursive and dependent processes.

Solve is the method which perform the proper call to the resolution methods (heuristics and solvers).

Define main process

└── define_main_process
   └── SeveralSolutions
      └── Repetitions
         └── define_process

Define process

└── define_process
   ├── SplitClustering
   |   └── define_process
   ├── Dichotomous
   |   └── define_process
   └── solve

Solve

└── solve
   ├── PeriodicVisits
   ├── Heuristics
   └── Wrapper::solve
      ├── demo
      ├── ortools
      └── vroom

Examples

Generate client

A client class could be generated using swagger-codegen v2.X. At this purpose, the current master and dev branches generates incorrect documentation.

The client can be generated using the following JSON: spec_file.json

To generate the associated Ruby gem:

java -jar modules/swagger-codegen-cli/target/swagger-codegen-cli.jar generate -i spec_file.json -l ruby -o optimizer-client -DgemName=optimizer-client

This gives the following project: Optimizer-Client

Languages also available with swagger-codegen:

ActionScript, Ada, Apex, Bash, C# (.net 2.0, 3.5 or later), C++ (cpprest, Qt5, Tizen), Clojure, Dart, Elixir, Elm, Eiffel, Erlang, Go, Groovy, Haskell (http-client, Servant), Java (Jersey1.x, Jersey2.x, OkHttp, Retrofit1.x, Retrofit2.x, Feign, RestTemplate, RESTEasy, Vertx, Google API Client Library for Java, Rest-assured), Kotlin, Lua, Node.js (ES5, ES6, AngularJS with Google Closure Compiler annotations) Objective-C, Perl, PHP, PowerShell, Python, R, Ruby, Rust (rust, rust-server), Scala (akka, http4s, swagger-async-httpclient), Swift (2.x, 3.x, 4.x, 5.x), Typescript (Angular1.x, Angular2.x, Fetch, jQuery, Node)

User UI

Some UI are available in order to test the features of the API using JSON or CSV files.

  • http://localhost:1791/index.html?api_key=demo lets you transmit a JSON file corresponding to the Optimizer-API VRP format.
  • http://localhost:1791/scheduling.html?api_key=demo expects multiple CSV files corresponding to the main concepts of Optimizer-API and a JSON file defining the expected configuration applied to solve the VRP. Some exemple files are available in the examples folder.
  • http://localhost:1791/pickup_delivery.html?api_key=demo is a deprecated UI using our legacy CSV format which has no direct correspondance with the API.
  • http://localhost:1791/result.html?api_key=demo allows to display a solution and eventually display the polylines if requested in the configuration.