java - すべてのルートで乗客の車両滞在時間を最小限に抑える

Question

乗客が車内で過ごす時間を最小限にしたい。

でのピックアップLEFTと でのピックアップがCENTERあり、両方が に向かう場合、は に向かう途中にあるため、車両が最初にBOTTOMピックアップする必要があります。LEFTCENTERBOTTOM

これを優先するように JSprit に指示するにはどうすればよいですか?

次の簡単な例を使用して、 からpickupShipmentまでの車両での合計時間にペナルティを課す RouteConstraint を実装してみました。deliverShipment

import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.algorithm.selector.SelectBest;
import com.graphhopper.jsprit.core.algorithm.state.StateManager;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.constraint.ConstraintManager;
import com.graphhopper.jsprit.core.problem.constraint.SoftRouteConstraint;
import com.graphhopper.jsprit.core.problem.job.Shipment;
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TimeWindow;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import junit.framework.TestCase;

import java.util.LinkedList;

public class PenalizeExtraTimeInVehicleTest extends TestCase {

    final Location LEFT = Location.newInstance(10.0, 50.0);
    final Location CENTER = Location.newInstance(50.0, 50.0);
    final Location BOTTOM = Location.newInstance(50.0, 90.0);

    public void testPickUpWithoutWastingTime() {
        VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
                .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
                .addVehicle(VehicleImpl.Builder.newInstance("V-1")
                        .setStartLocation(BOTTOM)
                        .build())
                .addJob(Shipment.Builder.newInstance("Center_to_Bot")
                        .setPickupTimeWindow(TimeWindow.newInstance(100.0, 200.0))
                        .setDeliveryTimeWindow(TimeWindow.newInstance(200.0, 300.0))
                        .setPickupLocation(CENTER)
                        .setDeliveryLocation(BOTTOM)
                        .build())
                .addJob(Shipment.Builder.newInstance("Left_to_Bot1") // if this doesn't end with "1" it will be picked up first
                        .setPickupTimeWindow(TimeWindow.newInstance(100.0, 200.0))
                        .setDeliveryTimeWindow(TimeWindow.newInstance(200.0, 300.0))
                        .setPickupLocation(LEFT)
                        .setDeliveryLocation(BOTTOM)
                        .build())
                .build();


        final StateManager stateManager = new StateManager(vrp);
        final ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
        constraintManager.addConstraint(new SoftRouteConstraint() {
            /**
             * Penalize for total time in vehicle for all passengers in a route.
             */
            @Override
            public double getCosts( JobInsertionContext insertionContext ) {
                LinkedList<Double> stack = new LinkedList<>();
                double timeInVehicle = 0.0;
                for ( TourActivity eachAct : insertionContext.getRoute().getActivities() ) {
                    if ( "pickupShipment".equals(eachAct.getName())) {
                        stack.push(eachAct.getEndTime());
                    } else if ("deliverShipment".equals(eachAct.getName())) {
                        final Double popped = stack.pop();
                        timeInVehicle += eachAct.getArrTime() - popped;
                    }
                }
                return timeInVehicle;
            }
        });
        final VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(vrp)
                .setStateAndConstraintManager(stateManager, constraintManager)
                .buildAlgorithm();

        VehicleRoutingProblemSolution solution = new SelectBest().selectSolution(algorithm.searchSolutions());

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

        final TourActivity firstActivity = solution.getRoutes().iterator().next().getActivities().get(0);
        assertEquals("Left_to_Bot", ((TourActivity.JobActivity) firstActivity).getJob().getId());
    }

}

これにより、以下の結果が得centerられleftます。

Job.idまた、結果に影響することにも注意してください。名前を変更Left_to_Bot1するLeft_to_Botと、最初に取得されます。

+--------------------------------------------------------------------------------------------------------------------------------+
| detailed solution                                                                                                              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | V-1                  | start                 | -               | undef           | 0               | 0               |
| 1       | V-1                  | pickupShipment        | Left_to_Bot1    | 57              | 100             | 57              |
| 1       | V-1                  | pickupShipment        | Center_to_Bot   | 140             | 140             | 97              |
| 1       | V-1                  | deliverShipment       | Left_to_Bot1    | 180             | 200             | 137             |
| 1       | V-1                  | deliverShipment       | Center_to_Bot   | 200             | 200             | 137             |
| 1       | V-1                  | end                   | -               | 200             | undef           | 137             |
+--------------------------------------------------------------------------------------------------------------------------------+