Possible to implement a capaciated VRP with multiple picks and single drop using OptaPy?

Skip to first unread message

Saugata Paul

Dec 14, 2022, 3:14:05 AM12/14/22
to OptaPlanner development


Hello everyone,

I am trying to solve a capacitated vehicle routing problem where the problem formulation is as follows. Please refer to the attached images for clarity.


The vehicle should leave a depot, traverse through the nodes, collect the waste from those nodes,  and then dump it to the nearest dumping zone once the vehicle carrying capacity has maxed out. Consider this as a multi-depot vrp, with multiple picks and a single delivery for each vehicle, after the delivery, the vehicle should return to the dumping zone.

1. I have created a dummy network of 50 nodes (incomplete graph) in Python using the networkX package. The dummy network of nodes is represented by the attached diagrams diagrams.
2. I have randomly chosen Nodes AJ, A, G, R as vehicle starting points/depots. (Highlighted in Yellow)
3. I have randomly chosen F, AQ, AA as the  dumping zones.
4. Each node can have certain demands, which is a representation of the amount of waste a vehicle can collect from that node.
5. Each depot has fixed number of vehicles, and each vehicle have a fixed carrying capacity, beyond which it will dump the waste to the nearest dumping zone. After dumping the waste, the vehicle can return to the original start depot (if there's no more waste left to clean)

Below are some constraints:

1. Network layout is fixed.
2. Depot & Dumping zone locations are fixed.
3. Number of vehicle in each dumping zone is fixed.
4. Carrying capacity of each vehicle is fixed for now.
5. Edge weight represents the amount/volume of waste present in a edge.
6. Vehicle can only travel between adjacent nodes and not jump over a node. For example, according to the diagrams, it can travel from A to B, B to C but not directly from A to C. For a vehicle to travel from A to C, it has to follow these paths --> A to B and B to C.

I am trying to solve this using Python, and recently came across OptaPy. But there are very limited resources for this for me to refer. I want to understand if this problem statement can be solved using OptaPy, by including all the constraint's that I have mentioned? Can anyone kindly point me to some resources for Python implementations? Any help on this would be hugely appreciated.

Saugata Paul.
Reply all
Reply to author
0 new messages