hschneid / xfvrp Goto Github PK

When adding vehicle restrictions to a customer the VRPPreCheckService crashes with following stack trace:

Caused by: java.lang.UnsupportedOperationException at java.util.AbstractList.remove(AbstractList.java:161) at java.util.AbstractList$Itr.remove(AbstractList.java:374) at java.util.AbstractCollection.remove(AbstractCollection.java:293) at xf.xfvrp.opt.init.precheck.vrp.VRPPreCheckService.removeNode(VRPPreCheckService.java:93) at xf.xfvrp.opt.init.precheck.vrp.VRPPreCheckService.checkVehicleType(VRPPreCheckService.java:75) at xf.xfvrp.opt.init.precheck.vrp.VRPPreCheckService.precheck(VRPPreCheckService.java:57)

Idea:

• Each depot defines his own vehicle type.
• Then HVRP is compatible with MDVRP

Hello,,
how can i find ReportBuilder class

• Remove giant route completely
  • Operators and usage in tests :-(
• Preset solution: It shall be possible to determine the depot
• Randomized solution builder for checking out GRASP
• New operator: Bordered Segment Exchange O(n^2)
• Route-based operator: Cyclic Transfer with 3 nodes

Dependent on the choosen vehicle or the current start depot, the end depot should be another one.

The user must specify this in input data.

Motivation: For multi period VRP it could make sense, that vehicle start their day at regional depot and finish at central depot.

NormalizeSolutionService

Caused by: java.lang.ArrayIndexOutOfBoundsException: 3 at xf.xfvrp.report.RouteReportSummary.setPickupLoad(RouteReportSummary.java:134) at xf.xfvrp.report.RouteReportSummary.add(RouteReportSummary.java:109) at xf.xfvrp.report.RouteReport.add(RouteReport.java:46) at xf.xfvrp.report.build.ReportBuilder.getRouteReport(ReportBuilder.java:53) at xf.xfvrp.report.build.ReportBuilder.getReport(ReportBuilder.java:40) at xf.xfvrp.opt.FullRouteMixedFleetHeuristic.execute(FullRouteMixedFleetHeuristic.java:67) at xf.xfvrp.XFVRP.executeRoutePlanning(XFVRP.java:81)

The next step of bigger neighborhood would be the two segment move.
Choose two segments and choose two destinations
Move segments to destinations

Size: n^4

Goal: If all other NS are run, this NS could jump into a next area of improvements

Restrictions:

• segments must not overlap
• dst's must not be in segments
• one segment is leading, so that both segments could have same dst
• Maybe split search phase for segments on different routes and same route

Todo

• It is possible to assign a boolean value, where for each replenishment location it can be setup, if a certain capacity type will be replenished.

This makes sense for complex simulations, where trucks have driver restrictions and capacity restrictions.

Hint: context has the routes and no giant route. Like evaluation service.

Todo

• There should be more than 3 capacities and also checked
• Vehicle's should can assign separate capacity for PICKUP or DELIVERY or MIXED (if truck contains both types of a certain capacity type)

Changes in ReportBuilder and ErrorSummary so that Solution.getGiantRoute is not called.

Use of getRoutes instead.

Could you please invoke deployment of 11.4.1 to maven repository?

Implementation of presettings seems to be buggy. For demonstration, I've added a new test instance in branch "test_instances". Just try my test test_presets_and_timewindows(). However, resulting tours seem not to be optimized and time window constraints are violated.

Instead of testing every single method separatly, tests should cover wider range.

Contraint tests should be done with complete XFVRP object instead of just using the inner evaluation function. This leads to duplicate tests and blind spots between the tested modules.

It is nearly the same and duplicate code. A shame!

Add xfvrp to maven central repository

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?

Currently all NS operators are looking into the distances of nodes.
The number of routes is not checked at search phase.
So, the sort phase will leverage solutions with less distance, but not with fewer routes.
Or more over: A solution which adds a new route will be preferred against a solution with same nbr of routes and less distances gain.

h3. Possible concepts

• In search phase adding a route or removing a route are counted and measured by cost function.
• If src is full and dst is empty +1
• If src segment contains all nodes of route and dst is not empty -1
• ...

I wonder if it’s possible to simulate not only a planning day but a planning week. The Input consists of orders from the whole week. The Depot has closing times from let’s say 7pm up to 6am. The vehicle is to return to the Depot before closing time and may start at the next day at depot opening time. Every order or customer stop has a certain time window. For example if a customer needs to be delivered on Wednesday the time window could be starting at 24h x 2 plus 6h and close six hours later.

Description
The transformation of Solution to Node[] (aka giant route) is heavy. To improve this, the check method should check with the Solution.

Requirements

• The Solution needs to methods to get access to Nodes of routes.
• Check method needs to be adapted. No need to check, if new route begins. Check of empty routes is easier.

Selecting only routes with more than accepted utilization (not for last vehicle type)

Currently the search phase of neighborhood search puts all improving steps into a List. After the search phase there is a dedicated sort. With profiler we can see, that sort phase is taking most of the time of optimization run.

To improve the performance, it would be possible to add each improving step into a heap which has cost of O(log n). Afterwards in check phase it pulls results on after another from the top of heap, which has cost of max O(n log n).

This could be done as PoC, because I'm not sure, if this helps a lot. :-)