Bad result to problem

avanturnick · September 2, 2016, 12:09pm

hI.

I’m using JSPRIT library to solve some routing problems - that’s obvious

In case of big problems - lik 50+ stops it works good - it’s hard to find some issues, but when I try to use it on small problems like 9 stops, it gets me strange results, like it orders me to go back and forth in some cases.

I’m using time cost matrix to solve my problems, and experiment with different algorithms, and iterations, and fleet size

Did you had similar problems? or maybe you have some pointers what to do?

thanks

stefan · September 2, 2016, 1:53pm

Do you use Jsprit.createAlgorithm(...)?

avanturnick · September 2, 2016, 2:24pm

Thank you for participation Stefan:)

Yes, I have created app that uses all types of algorithms from JSPRIT:

GreedySchrimpfFactory
SchrimpfFactory
Jsprit

testing them all, I have same result - telling me to go in circle:

it tells me to go back to stop number 5 - even thou it’s on the way.

PS - sorry for bad quality - I got it from front tester
PS 2 - stop 2 and 3 are in same spot

stefan · September 2, 2016, 2:39pm

Ok. Lets try to reproduce this. Do you get the same results when using Harversine, i.e. do not use a matrix but GreatCircleCosts.

avanturnick · September 2, 2016, 3:10pm

nope - haven’t used that.

I use VehicleRoutingTransportCostsMatrix.

avanturnick · September 2, 2016, 3:11pm

if you want to reproduce I can log my cost matrix - it’s small, it’s just 8 stops

avanturnick · September 2, 2016, 3:56pm

idFrom=’-1’, idTo=‘16823128’, distance=46.75, time=51.88
idFrom=’-1’, idTo=‘16823136’, distance=60.65, time=51.52
idFrom=’-1’, idTo=‘16823133’, distance=70.67, time=57.92
idFrom=’-1’, idTo=‘16823132’, distance=71.62, time=60.2
idFrom=’-1’, idTo=‘16823134’, distance=73.08, time=59.25
idFrom=’-1’, idTo=‘16830703’, distance=74.73, time=67.28
idFrom=’-1’, idTo=‘16830708’, distance=82.06, time=66.55
idFrom=‘16823128’, idTo=‘16823136’, distance=8.71, time=31.0
idFrom=‘16823128’, idTo=‘16823133’, distance=21.9, time=36.62
idFrom=‘16823128’, idTo=‘16823132’, distance=21.45, time=39.28
idFrom=‘16823128’, idTo=‘16823134’, distance=23.68, time=36.02
idFrom=‘16823128’, idTo=‘16830703’, distance=26.91, time=48.38
idFrom=‘16823128’, idTo=‘16830708’, distance=40.86, time=59.4
idFrom=‘16823132’, idTo=‘16823133’, distance=1.22, time=4.0
idFrom=‘16823132’, idTo=‘16830703’, distance=4.97, time=12.72
idFrom=‘16823132’, idTo=‘16823134’, distance=8.21, time=18.37
idFrom=‘16823132’, idTo=‘16823136’, distance=12.49, time=23.12
idFrom=‘16823132’, idTo=‘16830708’, distance=42.9, time=44.2
idFrom=‘16823133’, idTo=‘16830703’, distance=5.39, time=13.62
idFrom=‘16823133’, idTo=‘16823134’, distance=7.27, time=18.53
idFrom=‘16823133’, idTo=‘16823136’, distance=11.54, time=20.83
idFrom=‘16823133’, idTo=‘16830708’, distance=41.97, time=44.35
idFrom=‘16823134’, idTo=‘16830703’, distance=9.02, time=22.25
idFrom=‘16823134’, idTo=‘16823136’, distance=13.94, time=22.22
idFrom=‘16823134’, idTo=‘16830708’, distance=36.77, time=35.62
idFrom=‘16823136’, idTo=‘16830703’, distance=20.07, time=35.77
idFrom=‘16823136’, idTo=‘16830708’, distance=51.24, time=48.88
idFrom=‘16830703’, idTo=‘16830708’, distance=43.0, time=47.95

avanturnick · September 2, 2016, 5:35pm

got better image:

stefan · September 2, 2016, 6:40pm

Can you also send which id corresponds to which marker?

avanturnick · September 7, 2016, 9:29am

Hi Stefan - sorry for long time with no response - I wanted to test some solutions.

Here is picture with marked ID’s:

jie31best · September 7, 2016, 10:12am

when I use your cost matrix, I get the following solution. It is different from your picture and probably is what you expect.

±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 7 |
| noServices | 7 |
| noShipments | 0 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 118.97999999999999 |
| noVehicles | 1 |
| unassgndJobs | 0 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | v | start | - | undef | 0 | 0 |
| 1 | v | service | 16823128 | 52 | 52 | 47 |
| 1 | v | service | 16823136 | 83 | 83 | 55 |
| 1 | v | service | 16823133 | 104 | 104 | 67 |
| 1 | v | service | 16823132 | 108 | 108 | 68 |
| 1 | v | service | 16830703 | 120 | 120 | 73 |
| 1 | v | service | 16823134 | 143 | 143 | 82 |
| 1 | v | service | 16830708 | 178 | 178 | 119 |
| 1 | v | end | - | 178 | undef | 119 |
±-------------------------------------------------------------------------------------------------------------------------------+

avanturnick · September 7, 2016, 10:14am

yep. That’s correct solution. Can you post code for that please?

jie31best · September 7, 2016, 10:26am

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .build();
    VehicleImpl v = VehicleImpl.Builder.newInstance("v")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance("-1"))
            .build();
    Service s1 = Service.Builder.newInstance("16823128")
            .setLocation(Location.newInstance("16823128"))
            .build();
    Service s2 = Service.Builder.newInstance("16823132")
            .setLocation(Location.newInstance("16823132"))
            .build();
    Service s3 = Service.Builder.newInstance("16823133")
            .setLocation(Location.newInstance("16823133"))
            .build();
    Service s4 = Service.Builder.newInstance("16823134")
            .setLocation(Location.newInstance("16823134"))
            .build();
    Service s5 = Service.Builder.newInstance("16823136")
            .setLocation(Location.newInstance("16823136"))
            .build();
    Service s6 = Service.Builder.newInstance("16830703")
            .setLocation(Location.newInstance("16830703"))
            .build();
    Service s7 = Service.Builder.newInstance("16830708")
            .setLocation(Location.newInstance("16830708"))
            .build();
    VehicleRoutingTransportCostsMatrix costsMatrix =
            VehicleRoutingTransportCostsMatrix.Builder.newInstance(true)
                    .addTransportDistance("-1", "16823128", 46.75)
                    .addTransportTime("-1", "16823128", 51.88)
                    .addTransportDistance("-1", "16823136", 60.65)
                    .addTransportTime("-1", "16823136", 51.52)
                    .addTransportDistance("-1", "16823133", 70.67)
                    .addTransportTime("-1", "16823133", 57.92)
                    .addTransportDistance("-1", "16823132", 71.62)
                    .addTransportTime("-1", "16823132", 60.2)
                    .addTransportDistance("-1", "16823134", 73.08)
                    .addTransportTime("-1", "16823134", 59.25)
                    .addTransportDistance("-1", "16830703", 74.73)
                    .addTransportTime("-1", "16830703", 67.28)
                    .addTransportDistance("-1", "16830708", 82.06)
                    .addTransportTime("-1", "16830708", 66.55)
                    .addTransportDistance("16823128", "16823136", 8.71)
                    .addTransportTime("16823128", "16823136", 31.0)
                    .addTransportDistance("16823128", "16823133", 21.9)
                    .addTransportTime("16823128", "16823133", 36.62)
                    .addTransportDistance("16823128", "16823132", 21.45)
                    .addTransportTime("16823128", "16823132", 39.28)
                    .addTransportDistance("16823128", "16823134", 23.68)
                    .addTransportTime("16823128", "16823134", 36.02)
                    .addTransportDistance("16823128", "16830703", 26.91)
                    .addTransportTime("16823128", "16830703", 48.38)
                    .addTransportDistance("16823128", "16830708", 40.86)
                    .addTransportTime("16823128", "16830708", 59.4)
                    .addTransportDistance("16823132", "16823133", 1.22)
                    .addTransportTime("16823132", "16823133", 4.0)
                    .addTransportDistance("16823132", "16830703", 4.97)
                    .addTransportTime("16823132", "16830703", 12.72)
                    .addTransportDistance("16823132", "16823134", 8.21)
                    .addTransportTime("16823132", "16823134", 18.37)
                    .addTransportDistance("16823132", "16823136", 12.49)
                    .addTransportTime("16823132", "16823136", 23.12)
                    .addTransportDistance("16823132", "16830708", 42.9)
                    .addTransportTime("16823132", "16830708", 44.2)
                    .addTransportDistance("16823133", "16830703", 5.39)
                    .addTransportTime("16823133", "16830703", 13.62)
                    .addTransportDistance("16823133", "16823134", 7.27)
                    .addTransportTime("16823133", "16823134", 18.53)
                    .addTransportDistance("16823133", "16823136", 11.54)
                    .addTransportTime("16823133", "16823136", 20.83)
                    .addTransportDistance("16823133", "16830708", 41.97)
                    .addTransportTime("16823133", "16830708", 44.35)
                    .addTransportDistance("16823134", "16830703", 9.02)
                    .addTransportTime("16823134", "16830703", 22.25)
                    .addTransportDistance("16823134", "16823136", 13.94)
                    .addTransportTime("16823134", "16823136", 22.22)
                    .addTransportDistance("16823134", "16830708", 36.77)
                    .addTransportTime("16823134", "16830708", 35.62)
                    .addTransportDistance("16823136", "16830703", 20.07)
                    .addTransportTime("16823136", "16830703", 35.77)
                    .addTransportDistance("16823136", "16830708", 51.24)
                    .addTransportTime("16823136", "16830708", 48.88)
                    .addTransportDistance("16830703", "16830708", 43.0)
                    .addTransportTime("16830703", "16830708", 47.95)
                    .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addJob(s1).addJob(s2).addJob(s3).addJob(s4).addJob(s5).addJob(s6).addJob(s7)
            .addVehicle(v)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .setRoutingCost(costsMatrix)
            .build();

    VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(vrp).buildAlgorithm();

    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());

    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);

avanturnick · September 8, 2016, 11:55am

thank you. after careful examining I’ve found problem.

I’ve set cost matrix to not symmetric, plus I made my own matrix implementation that can work with incomplete cost matrix. And that was the problem here - problem had complete symmetric matrix.