Balancing number of nodes being visited among vehicles

[its-rav]

Dear all,
Here is my problem:
- I have multiple pick up stations with demands and several delivery stations
- Pick up stations can share a similar delivery station
- Delivery stations can act as a pick up station
Firstly, I can split a pick up station to dummy nodes with one demand so that my vehicles can technically visit same pick up node and pick up packages (this one happen when I generate distance matrix)
Secondly, I split create a dummy delivery station for each demand/pick up station and create pickupdeli constrain on its index. To be specific.
Generally, for example,
- I have 7 nodes : (A), (B), (C), (D), (E) , (F) with (D) as depot and (A), (B) as delivery node
- with demands: 2 (B) -> (A), [2 packages at station B need to delivery to A]
1 (C) -> (B),
* 3 (C) -> (A),
2 (E) -> (A),
1 (F) -> (A),
1 (F) -> (B)
- number of vehicle: 3 (capacity: 20 for each vehicle)
What I do is split nodes that have demand > 1 [* 3 (C) -> (A)] into [1 (C) -> (A),1 (C) -> (A),1 (C) -> (A)].
So that, as result, I have 10 dummy nodes as delivery node, 10 nodes at pickup nodes and a depot node.

The problem is after the program excecuted, the result return only a path for a single vehicle which traversed through all nodes.
So that I try to add a CounterDimension and what it did is to limit the number of nodes each vehicle visit and balance it. Then the program return no result at all

Please help me with my problem, thank you in advance.
Feel free to correct anything.

public static RoutingResponse Solve(RoutingDataModel data)
        {
            // Create Routing Index Manager
            RoutingIndexManager manager = new RoutingIndexManager(
                data.DistanceMatrix.GetLength(0),
                data.VehicleNumber,
                data.Depot);

            // Create Routing Model.
            RoutingModel routing = new RoutingModel(manager);

            //add dimensions
            InintDimension(data, routing, manager);

            // Setting search parameters.
            RoutingSearchParameters searchParameters = InitSearchParameters();

            // Solve the problem.
            Assignment solution = routing.SolveWithParameters(searchParameters);

            //Generate response
            RoutingResponse response = GetRoutesResponse(data, routing, manager, solution);

            return response;
        }

private static void InintDimension(RoutingDataModel data, RoutingModel routing, RoutingIndexManager manager)
        {
            AddDemandsDimension(CAPACITY_DIM_NAME, data, routing, manager);

            var distanceDimension=AddDistanceDimension(DISTANCE_DIM_NAME, data, routing, manager);

            //Add node restriction to vehicles
            Solver solver = routing.solver();
            for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++)
            {
                long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
                long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
                routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
                solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex)));
                solver.Add(solver.MakeLessOrEqual(distanceDimension.CumulVar(pickupIndex),
                                                  distanceDimension.CumulVar(deliveryIndex)));
            }

           AddCounterDimension(COUNTER_DIM_NAME, data, routing, manager);
        }

private static RoutingDimension AddDemandsDimension(string dimName, RoutingDataModel data, RoutingModel routing, RoutingIndexManager manager)
        {
            int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
            {
                // Convert from routing variable Index to demand NodeIndex.
                var fromNode = manager.IndexToNode(fromIndex);
                return data.Demands[fromNode];
            });
            routing.AddDimensionWithVehicleCapacity(demandCallbackIndex,
                                                    0, /*null capacity slack*/
                                                    data.VehicleCapacities, /* vehicle maximum capacities*/
                                                    true,                   /* start cumul to zero*/
                                                    dimName);
            RoutingDimension dim = routing.GetMutableDimension(dimName);
            return dim;
        }
private static RoutingDimension AddDistanceDimension(string dimName, RoutingDataModel data, RoutingModel routing, RoutingIndexManager manager)
        {
            // Create and register a transit callback.
            int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
            {
                // Convert from routing variable Index to distance matrix NodeIndex.
                var fromNode = manager.IndexToNode(fromIndex);
                var toNode = manager.IndexToNode(toIndex);
                return data.DistanceMatrix[fromNode, toNode];
            });

            // Define cost of each arc.
            routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

            // Add Distance constraint.
            routing.AddDimension(transitCallbackIndex,
                0,
                Int32.MaxValue,
                true, /* start cumul to zero*/
                dimName);
            RoutingDimension distanceDimension = routing.GetMutableDimension(dimName);
            //distanceDimension.SetGlobalSpanCostCoefficient(100);

            return distanceDimension;
        }
private static RoutingDimension AddCounterDimension(string dimName, RoutingDataModel data, RoutingModel routing, RoutingIndexManager manager)
        {
            long min = data.GetMinNodesVisit();//1
            long max = data.GetMaxNodesVisit();//(total nodes / vehicle num)+2
            int counterCallbackIndex = routing.RegisterUnaryTransitCallback((long index) => { return 1; });
            routing.AddDimension(
                counterCallbackIndex,
                0,  // null capacity slack
                max,  // vehicle maximum capacities
                true,  // start cumul to zero
                dimName);

            RoutingDimension counterDimension = routing.GetDimensionOrDie(dimName);
            for (int vehicleId = 0; vehicleId < data.VehicleNumber; vehicleId++)
                counterDimension.CumulVar(routing.End(vehicleId))
                    .SetMin(min);

            return counterDimension;
        }

[its-rav]

Well, turn out my FirstSolutionStrategy was GlobalCheapestArc. Changed it to PathMostConstrainedArc and everything work fine. By the way, can someone explain me how different between FirstSolutionStrategy options and LocalSearchMetaheuristic options, kinda use it random.

private static RoutingSearchParameters InitSearchParameters()
        {
            RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();

            searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.GlobalCheapestArc;
            searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
            searchParameters.TimeLimit = TIME_LIMIT;
            searchParameters.LogSearch = LOG_SEARCH;
            //searchParameters.LogCostOffset = LOG_COST_OFFSET;
            //searchParameters.LogCostScalingFactor = LOG_COST_SCALING_FACTOR;
            //searchParameters.LogTag = LOG_TAG;

            return searchParameters;

        }

[lperron]

First solution strategies try to find the first solution. When you have a first solution, local search starts. It starts exploring neighborhoods of the current solution. The meta-heuristics control which move you accept to make. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le ven. 5 févr. 2021 à 18:08, voasd <[email protected]> a écrit :

…

Well, turn out my FirstSolutionStrategy was GlobalCheapestArc. Changed it to PathMostConstrainedArc and everything work fine. By the way, can someone explain me how different between FirstSolutionStrategy options and LocalSearchMetaheuristic options, kinda use it random. private static RoutingSearchParameters InitSearchParameters() { RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.GlobalCheapestArc; searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch; searchParameters.TimeLimit = TIME_LIMIT; searchParameters.LogSearch = LOG_SEARCH; //searchParameters.LogCostOffset = LOG_COST_OFFSET; //searchParameters.LogCostScalingFactor = LOG_COST_SCALING_FACTOR; //searchParameters.LogTag = LOG_TAG; return searchParameters; } — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2383 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3OQSVI6ZBXW3D6QSFLS5QQYHANCNFSM4XEXSMCQ> .