GraphHopper.com | Forum | GitHub | Maps | Blog

Consecutive Services with morning and afternoon time windows


#1

I often have this case of vehicle routing problem:

A bunch of services with a time window for the morning (e.g. 8:00 - 12:30)

And a bunsch of services with a time window for the afternoon (eg. 12:30 - 17:00)

The vehicle has a time window from 8:00 till 17:00 then.

Now when the services for the afternoon do not fill the complete afternoon time window, they get placed in the middle of the time window (e.g from 13:30 - 16:00).

Is there any parameter, that causes all services to be connected to each other, when possible.

The first idea I had, was to set the vehicles departure and arrival time after the first algorithm run according to the number of services it gets assigned to. But then I need a second run, which consumes unneccessary time.

Does someone have a simple idea, how to get rid of this behaviour?

Best regards


#2

Hi Max,

The issue is not easy to understand properly. What exactly do you mean by “the middle of the time window (e.g from 13:30 - 16:00)”? Is this some kind of constraint in your solution that you haven’t specified? Can you give a simple but specific example of what’s not working?

Thanks


#3

Sorry for the complicated description. I have build a simple example:

VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType");
VehicleType             vehicleType        = vehicleTypeBuilder.build();


VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");
vehicleBuilder.setStartLocation(Location.newInstance(10, 10));
vehicleBuilder.setType(vehicleType);
vehicleBuilder.setEarliestStart(0);
vehicleBuilder.setLatestArrival(100);
VehicleImpl vehicle = vehicleBuilder.build();


Service service1 = Service.Builder.newInstance("1")
                                  .setLocation(Location.newInstance(10.5, 10.7))
                                  .addTimeWindow(0, 50)
                                  .setServiceTime(10)
                                  .build();
Service service2 = Service.Builder.newInstance("2")
                                  .setLocation(Location.newInstance(10.5, 10.13))
                                  .addTimeWindow(0, 50)
                                  .setServiceTime(10)
                                  .build();

Service service3 = Service.Builder.newInstance("3")
                                  .setLocation(Location.newInstance(10.15, 10.7))
                                  .addTimeWindow(50, 100)
                                  .setServiceTime(10)
                                  .build();
Service service4 = Service.Builder.newInstance("4")
                                  .setLocation(Location.newInstance(10.15, 10.13))
                                  .addTimeWindow(50, 100)
                                  .setServiceTime(10)
                                  .build();


VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle);
vrpBuilder.addJob(service1).addJob(service2).addJob(service3).addJob(service4);


VehicleRoutingProblem problem = vrpBuilder.build();

	/*
 * get the algorithm out-of-the-box.
	 */
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

	/*
 * and search a solution
	 */
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

	/*
 * get the best
	 */
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);

This results in:

+--------------------------------------------------------------------------------------------------------------------------------+
| detailed solution                                                                                                              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | vehicle              | start                 | -               | undef           | 0               | 0               |
| 1       | vehicle              | service               | 2               | 1               | 11              | 1               |
| 1       | vehicle              | service               | 1               | 11              | 21              | 1               |
| 1       | vehicle              | service               | 3               | 21              | 60              | 30              |
| 1       | vehicle              | service               | 4               | 61              | 71              | 31              |
| 1       | vehicle              | end                   | -               | 71              | undef           | 31              |
+--------------------------------------------------------------------------------------------------------------------------------+

As you can see, there is a big gap between jop 1 and 3. For me it would be better if job 2 would start at time 30,job 1 at time 40, job 3 at 50 and job 4 at 60. So the jobs are in a proper order, but they should be pulled together, so there is no waiting time between them.


#4

I am also having the same issue. In some places service time is huge like in above table. Are you able to resolve this problem.

In the 3rd item my service time is around 6hrs instead of 15mins.

|Start time|End Time |Order Sequence|
|09:32 |09:47 | 1|
|10:15 |10:30 | 2|
|11:17 |17:16 | 3|