# Generating a good initial solution for a problem

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:

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.

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.
• 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. Apr 16 at 16:06