Capacitated Vehicle Routing Problem (CVRP)

The Capacitated VRP (CVRP) is formulated on a graph \(G = (N, E)\), where \(N = \{0, 1, \ldots, n\}\) represents the set of nodes, with \(0\) denoting the depot and \(N_c = \{1, \ldots, n\}\) representing the customers. Each customer \(i \in N_c\) has a demand \(q_i\). The edges \(E\) connect pairs of nodes, and each edge \((i, j) \in E\) has a travel cost \(c_{ij}\) (e.g., distance or travel duration). A fleet of vehicles, each with a capacity \(Q\), departs from the depot to serve each of the customers exactly once and returns, with the objective of minimizing the total travel cost.

Observations

• location of the depot.
• locations and demand of each customer.
• current location of the vehicle.
• the remaining customer of the vehicle,

Constraints

• the tour starts and ends at the depot.
• each customer must be visited exactly once.
• the vehicle cannot visit customers exceed the remaining capacity.
• the vehicle can return to the depot to refill the capacity.

Finish Condition

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

Reward

• (minus) the negative length of the path.