Skip to content

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) adds an additional layer of complexity to CVRP by incorporating specific time frames during which deliveries or pickups must be made. Each customer has a designated time window, and vehicles must adhere to these timings, adding constraints that significantly impact route planning and scheduling. This problem is particularly crucial in urban logistics and services such as food delivery or home services, where timely operations are critical for customer satisfaction and regulatory compliance.

At each step, the agent chooses a customer to visit depending on the current location, the remaining capacity, and the service time. When the agent visits a customer, the remaining capacity is updated and there requires a service time. If the remaining capacity is not enough to visit any customer, the agent must go back to the depot. If the agent arrives at one customer before the starting of the service time, it has to wait until the starting time. The agent can not visit a customer outside the time windows. The cost is the length of the path.

Observations

  • location of the depot.
  • locations and demand of each customer.
  • current location of the vehicle.
  • the remaining customer of the vehicle.
  • the current time.
  • service durations of each location.
  • time windows of each location.

Constrains

  • the tour starts and ends at the depot.
  • each customer must be visited exactly once.
  • the vehicle cannot visit customers exceed the remaining customer.
  • the vehicle can return to the depot to refill the customer.
  • the vehicle must start the service within the time window of each location.

Finish Condition

  • the vehicle has visited all customers and returned to the depot.

Reward

  • (minus) the negative length of the path.