Skip to content

Latest commit

 

History

History
86 lines (62 loc) · 2.05 KB

README.md

File metadata and controls

86 lines (62 loc) · 2.05 KB

VRP Garbage Collection

The Capacitated, Multitrip with Time Windows Vehicle Routing Problem of Garbage Collection

Deposit: Starting and Ending sites from where a vehicle departs. Containers: Object used to hold garbage. Dump: Sites where the garbage is delivered. Vehicle: Garbage collector.

A vehicle's route:

Deposit -> Containers -> Dump -> [Containers -> Dump] -> Deposit

Restrictions:

  • Vehicle:
    • Time window:
      • Driver shift start.
      • Driver's shift end.
    • One dimensional Capacity.
    • Capacity can be vary between vehicles.
    • Goes to the Dump when reached the maximum capacity except the last trip.
      • Even when a better route can be found with not full vehicle.
    • Vehicles are empty at the Deposit and after departure of the Dump
    • Has to return to the original Deposit
    • Can not make U turns
    • If a Driver has time

Deposit:

  • Has a (lat , lon) location.
  • opens at 0
  • closes at infinity
  • As a Starting Site
    • can have a service time (currently is fixed to 0)
  • As an Ending Site
    • can have a service time (currently is fixed to 0)

Dump:

  • Has a (lat , lon) location.
  • opens at 0
  • closes at infinity
  • Has a service time.

Container:

  • Has a (lat , lon) location.
  • Has an opening time
  • Has an closing time
  • Has a Capacity
    • The units must match the vehicles Capacity units.

Others:

  • Visit Dump inmediately after Deposit is forbidden
  • Visit Deposit inmediately after a Container is forbidden

Implied restrictions:

  • City topoogy

From the point of view of the driver: Deposit and dump:

  • Opens at Driver's shift time start.
  • Closes at Driver's shift time end.

Data from Montevideo City is used for this development.

Dependencies

Currently:

  • glog - For logging
  • OSRM - Local shared server installed for coverage area.

TODO

  • Update To be used with OSRM v5
    • When the project started OSRM 0.3.3 was used.
  • Clean Code
    • Many trial & error were kept in the code.
  • Update code to C++14
  • Documentation