I am solving an extended version of VRP, namely prize collecting VRP with incomplete service. There are its characteristics:

  • It's a VRP where you collect prizes for each fullfilled demand
  • you don't have to visit all customers
  • you may deliver less than what the customer demands and the prize will be proportional to that amount
  • You however have to schedule routes that fullfill a lower bound on the total prize, denoted as $P_{min}$.

For my mathematical model, I defined the prize sum lower bound as 0,5 times the sum of all the prizes of a given instances.

Last week I have been working on developping a heuristic to tackle its complexity, everything works but I noticed that the quality gap between the heuristic and my exact method is very big. The issue here lies in generating an initial solution. This is the algorithm that I used to generate initial solutions, since the problem is fairly new I could not find any algorithms to get inspired with:

enter image description here

The issue lies with what I marked with red. To make it simply: What the first chunk of marked lines does is it generates a route for each vehicle in which we keep adding customers as long as the vehicle has the capacity for it.

Next the last line only considers routes where their total prize is higher than $P_{min}$.

Unless I set a very low number for $P_{min}$, my program does not pick any routes. What the best I could do was to divide $P_{min}$ with the number of vehicles $0,50 \times \frac{\sum\limits_{i \in I}{p_{i}} }{|K|}$ All of the instances that I have to play have customers with low rewards and high demands so even by hand, my algorithm will always generate a bad initial solution. Can anyone help me with a trick here ? The algorithm that I programed is a VNS that has the incomplete service mechanic embeded within it, so the issue is only in the initial solution.


1 Answer 1


If you set $P_{min}$ to half the sum of all prizes, you only get maximally 2 tours right? Therefore, it might not be surprising that you hardly get a feasible tour. Instead of calculating the saving based on distances, you could add customers based on the prize they add to the tour, or possibly a mix (ratio), which includes prize, distance and capacity.

Further, I would not be so sure if it really is the initial solution that leads to big quality gaps. A VNS should be able to improve the initial solution significantly. Make sure that your VNS can cope with temporary infeasible solutions.

  • $\begingroup$ Hello, thanks for responding. I had an idea that is close to what you mentioned. I cut down the customer's list by sorting them by a ratio of prize / demand, and then making it so that $P_{min}$ keeps adding up their prizes until it hits exactly 0,25 * the original total sum of prizes. my original implementation (Initial solution + VNS) had an objective function of 1500-1700, with this new modification I made a huge cut all the way to aprox 500-600. $\endgroup$
    – applethal
    Commented Apr 16 at 16:06
  • $\begingroup$ Sorry I am new here, still learning the forum's culture. Although I accept your answer, I also wanna welcome newer ideas if anyone wants to improve this whole thing further. $\endgroup$
    – applethal
    Commented Apr 17 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.