Unnecessary waiting time when considering time windows

[larsupb]

Using xfvrp with time windows currently leads to the follow situation:

Xfvrp schedules a vehicle in the way, that it arrives the first customer on its earliest possible opening time. Let's say, the customer opens at 200, then the vehicle will arive on 200. However, there may be more customers on the route which also have time windows. For example, if the second customer on the route has an opening time of 300, the vehicle would arrive on 250 (50 minutes for service time at first customer and travelling time towards second customer). So there is a waiting of 50 minutes, which isn't necessary at all. The vehicle could have startet its tour 50 minutes later.

Is it possible to minimize waiting time?

[HolgerSchneider]

I see, that we already can give a max waiting time to vehicle.

So, you request is valid, and I need to change the evaluation routine, so that it can detect the latest departure with min waiting time.

• If arrival time at Customer i is less than opening time
  • If closing time at Customer i - 1 is more than departure time
  • slack = MIN(i.openingTime - arrivalTime, i-1.closingTime - departureTime)
  • departureTime += slack
  • arrivalTime += slack

What do you think? Did I miss something?

[larsupb]

Looks good to me. Should give it a try.

[hschneid]

After some thinking, I have something more to discuss:

• Example scenario:
  • Deport times [0, 1000]
  • Drive times always 50 min
  • First customer times [100, 200]
  • Second customer times [200, 300]
• Easy thing: Transport departs at depot at 50 to reach first customer without waiting times
• Question thing: At first customer, transport would need to leave at 150 to minize waiting time. But transport cannot park at first customer to overgap the 50 min between 100 and 150. Isn't this also waiting time.
• From my point of view, it is only the move of waiting times before service to after service.

What do you think?