Multi-depot VRP


Hello Team,
I am working on the multidepot-VRP problem an extension of your practical example capacitated VRP. I want to make a model in which vehicles will depart from their depots to serve different customers and turn back to the same depot where it started from. I made a rough model but facing some sort of errors. Kindly check and help me to resolve my model.
I shall be really thankful to you.

Looking forward for your kind response.

Regards

25 replies

Userlevel 5
@Muhammad Furqan , your model does not have any data specifying which vehicle belongs to which depot. A parameter like

VehicleDepot(Vehicle-1, Depot-1) = 1, VehicleDepot(Vehicle-2, Depot-2) = 1, and so on is required.

After that, your binary variable can be indexed over the vehicle and customer locations (in and out) only as you already know the depot that vehicle belongs to. An additional constraint that the vehicle must leave and must enter the depot it belongs it required.
thanks for your response @mohansx
i have extended my working and add an element parameter which defines the vehicle location that which vehicle is parked at which depot. like you exemplify.
Further i worked in-degree and out-degree constraint as you mentioned but here i am facing issue that when i added these constraints vehicles are routing but only depot to depot location not going at customer location.
what you may suggest to run the model from depot to customer and then back to the same depot.
Userlevel 5
Do you have a constraint for each customer which enforces that the number of trucks visiting is at least one ? Something like

sum[(truck, location), binary(location, customer, truck)] >= 1

This could be = 1 if you want only a single truck to visit a customer
I have added this constraint but i am not getting the right result. like what i want that it each vehicle should depart and turn back to the customer. capacity not exceeded. each customer must be served.
i am sharing my working file, hope it will help you to understand the error.
Kindly load the data case to run the model
Userlevel 5
@Muhammad Furqan , based on the case you shared - all your vehicles are identical (all of them have 4000 capacity). Is that always the case ?

Then the attached model should be sufficient, review it. 2 nodes connected (represented by binary variable bvArc(i,j) ) can be interpreted as a truck leaving node i and going to node j.
@mohansx,
Thanks for your support.
I have checked your model, it is satisfying the objective function.
Yes, for each vehicle, capacity is taken 4000.
Yes, your proposed model (represented by binary variable bvArc(i,j) which is two index model while i am working with three index model like it was x(i,j,k).
With that case i want to get my objective function, where almost constraints are same.
each vehicle need to depart and turn back to the same depot. each customer must be served and capacity should not be exceeded.
kindly provide me the detail of 0 node which you used in the model . is that null nodes, which you used to satisfied the model objective.
Userlevel 5
kindly provide me the detail of 0 node which you used in the model . is that null nodes, which you used to satisfied the model objective.

I don’t understand what you mean by 0 node, can you elaborate please ?

Yes, the model I gave you is 2 index. You don’t need a 3 index model if all the trucks have the same capacity. After solving the 2 index model, count the number of outgoing arcs from each depot - that will give you the number of trucks used in that depot. Each closed loop (starting from a depot and ending at that depot) represents the route of a truck. Eg: Depot 1 - 3 - 5 - 7 - Depot 1 is the route of a truck. BvArc(Depot 1, 3), bvArc(3,5) , bvArc(5,7), bvArc(7, Depot 1) are all equal to 1.
I don’t understand what you mean by 0 node, can you elaborate please ?

@mohansx OK with the above mentioned statement, i understand that point.
Secondly, as i told i am working with the three index model, i need to add further things in the model but right now i was lacking with the some of my constraints to add in aimms and to run it. which you explained earlier with two index model.
But if the same model run through with the three index model with same constraints so it would be a great favor for me.
I appreciate your help and response you provided me till now.

Regards
Userlevel 5
@Muhammad Furqan

I modified the earlier model to work with 3 indices as you asked. Review attached project and let me know if you have any questions. I left comments for all variables and constraints.
@mohansx
Thanks for your response.
i have checked the model. working was good.
Kindly explain the process of post processing.
I am lacking to understand with that Identifier.

Regards
Userlevel 5
@Muhammad Furqan I simply used the identifiers in the Postprocessing section to visualize the results in the network object on Page 1. Arcs in a network object are 2 indexed but our variable has 3 indexes. Hence the postprocessing.
Thank you.
@mohansx working on the previous model.. i extended few things in the model and added pickup and delivery location in place of customers. and i wanted to serve the pickup location first then the delivery location. i added two of pickup constraint which will ensure to pickup first and then deliver.
pickup first Definition: sum(P, S(P,K)) <= sum(R, S(R,K)); and second keep things correct along the path Definition: S(i,K)+ servicetime(i) + traveltime(i,j) <= S(j,K);
but getting this error.
Userlevel 5
Your screenshot shows that there are infeasible combinations in the DemandBalance constraints. I cannot help without actually looking at what new variables and constraints you have added. perhaps try verifying that you removed invalid combinations using index domain conditions.
@mohansx well i have attached the relevant model.

Looking forward for your response.

Hi @Muhammad Furqan and @mohansx, currently i’m doing thesis and having same topic, but I’m facing error duplicate column. Could you help fix the issues..? 

Hi @Farhan Surury , Kindly please add details/definition for your variables, sets or parameters. 

Hi @Muhammad Furqan, I tried to adopt your model but why I can’t link the data between Parameter “numofvehicles” and Set “vehicles”. In parameter I already input the initial data, but it won’t show the number in Set…?

Here I attached my Model. Looking forward to your response..

well, @Farhan Surury    it depends on, how you are linking the parameter (number of vehicles) and set (vehicles). it may vary from model to model. 

As per my knowledge it can be linked as:

Set Vehicles {
    SubsetOf: Integers;
    Index: K;
    Definition: {
       
    }

 

Parameter Numberofvehicles {
    Range: integer;
    InitialData: 5 (number of vehicles using in the model)
    Comment: "total number of vehicles.";
}

Well  @Farhan Surury , I have checked your model. first, you need to create a link between vehicles and the number of vehicles as described above. Further, your vehicles are not able to meet your demand because the number of vehicles is too short as compared to your demand. you need to add more vehicles or increase the capacity of your vehicles and consider it more than your demand. 

otherwise, it will not work properly and violate the constraints (visitallcustomers & demandbalance). 

Thanks @Muhammad Furqan for your answer, somehow the link works properly after I retry to do as you mentioned above..

Based on the model, I want to create multi-compartment vehicle, do i have to define the demand of each of products..?

Well @Farhan Surury , I don't have an exact idea about your actual model but as per my understanding, yes you need to define your product line and its demand. Further, you can check heterogeneous vehicles routing problems with the multi-commodity flow for better understanding.   

Hi @Muhammad Furqan and @mohansx,

 

Can you help me how to set this constraint into AIMMS..?

 

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator