Originally posted by: Sulivan
Hello there I am studying vehicle routing problem incorporated with multi-trip, split delivery, time windows and heterogeneous fleet features. A set customers are to be served by a fleet of different vehicles, each of which is associated with a capacity, and allowed to perform multiple trips. There may exist customers whose demand is larger than the capacity of any vehicle, hence the demands are allowed to be splitly fulfilled by several deliverys. The time windows of customers are soft. That is, high penalty cost will added to the objective function if they are violated.
I formulated the problem with MILP and created a small sample problem with five customers (demands: [90 110 70 30 150]) and four vehicles (capacities: [50 100 30 20]). When I solve the problem, I noticed that in each trip, a vehicle either visit one customer, or all five customers. I'm not sure which constraints have caused this.
Looking at the solution. It is apparent that the objetive can be improved by having some routes visiting four or less customers (merging the splited delivery, which does not violate the capacity constraints). For example, the following solution (found by CPLEX):
[0 0 0 0 100] by V2
[0 0 20 0 0] by V4
[50 0 0 0 0] by V1
[8 60 3 28 1] by V2
[1 49 1 1 48] by V2
[1 1 46 1 1] by V1
[30 0 0 0 0] by V3
can be improved to:
[0 0 0 0 100]
[0 0 20 0 0]
[50 0 0 0 0]
[10 60 0 30 0]
[0 50 0 0 50]
[0 0 50 0 0]
[30 0 0 0 0]
However. When I add an arbitrary constraint to limit the maximum number of customers to be visited in each trip to be 4 or less, the problem becomes infeasible.
My model and .dat file are attached.
Can anybody help me with my formulation? Thank you in advance?
#DecisionOptimization#OPLusingCPLEXOptimizer