-
Notifications
You must be signed in to change notification settings - Fork 609
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
- Loading branch information
Showing
3 changed files
with
265 additions
and
8 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
156 changes: 156 additions & 0 deletions
156
jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/ruin/RuinTimeRelated.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,156 @@ | ||
| /* | ||
| * Licensed to GraphHopper GmbH under one or more contributor | ||
| * license agreements. See the NOTICE file distributed with this work for | ||
| * additional information regarding copyright ownership. | ||
| * | ||
| * GraphHopper GmbH licenses this file to you under the Apache License, | ||
| * Version 2.0 (the "License"); you may not use this file except in | ||
| * compliance with the License. You may obtain a copy of the License at | ||
| * | ||
| * http://www.apache.org/licenses/LICENSE-2.0 | ||
| * | ||
| * Unless required by applicable law or agreed to in writing, software | ||
| * distributed under the License is distributed on an "AS IS" BASIS, | ||
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
| * See the License for the specific language governing permissions and | ||
| * limitations under the License. | ||
| */ | ||
| package com.graphhopper.jsprit.core.algorithm.ruin; | ||
|
|
||
| import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem; | ||
| import com.graphhopper.jsprit.core.problem.job.Job; | ||
| import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute; | ||
| import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity; | ||
| import com.graphhopper.jsprit.core.util.NoiseMaker; | ||
| import org.slf4j.Logger; | ||
| import org.slf4j.LoggerFactory; | ||
|
|
||
| import java.util.ArrayList; | ||
| import java.util.Collection; | ||
| import java.util.List; | ||
|
|
||
|
|
||
| /** | ||
| * @author stefan schroeder | ||
| */ | ||
|
|
||
| public final class RuinTimeRelated extends AbstractRuinStrategy { | ||
|
|
||
| static class RelatednessToTourActivity { | ||
|
|
||
| final double time; | ||
|
|
||
| final TourActivity tourActivity; | ||
|
|
||
| final VehicleRoute route; | ||
|
|
||
| final double distance; | ||
|
|
||
| public RelatednessToTourActivity(double relatednessToTarget, double distance, TourActivity tourActivity, VehicleRoute route) { | ||
| this.time = relatednessToTarget; | ||
| this.distance = distance; | ||
| this.tourActivity = tourActivity; | ||
| this.route = route; | ||
| } | ||
| } | ||
|
|
||
| private static final Logger logger = LoggerFactory.getLogger(RuinTimeRelated.class); | ||
|
|
||
| private final VehicleRoutingProblem vrp; | ||
|
|
||
| private NoiseMaker noiseMaker = () -> 0; | ||
|
|
||
| public void setNoiseMaker(NoiseMaker noiseMaker) { | ||
| this.noiseMaker = noiseMaker; | ||
| } | ||
|
|
||
| public RuinTimeRelated(VehicleRoutingProblem vrp) { | ||
| super(vrp); | ||
| this.vrp = vrp; | ||
| this.ruinShareFactory = () -> (int) Math.max(50, Math.round(vrp.getJobs().size() * 0.3)); | ||
| logger.debug("initialise {}", this); | ||
| } | ||
|
|
||
| /** | ||
| * Removes a fraction of jobs from vehicleRoutes. | ||
| * <p> | ||
| * <p>The number of jobs is calculated as follows: Math.ceil(vrp.getJobs().values().size() * fractionOfAllNodes2beRuined). | ||
| */ | ||
| @Override | ||
| public Collection<Job> ruinRoutes(Collection<VehicleRoute> vehicleRoutes) { | ||
| List<Job> unassignedJobs = new ArrayList<>(); | ||
| int totalActivities = 0; | ||
| for (VehicleRoute route : vehicleRoutes) { | ||
| totalActivities += route.getActivities().size(); | ||
| } | ||
| if (totalActivities == 0) return unassignedJobs; | ||
| int randomIndex = random.nextInt(totalActivities); | ||
| int numActs = 0; | ||
| TourActivity targetActivity = null; | ||
| for (VehicleRoute route : vehicleRoutes) { | ||
| if (numActs + route.getActivities().size() < randomIndex) { | ||
| numActs += route.getActivities().size(); | ||
| } else { | ||
| for (TourActivity activity : route.getActivities()) { | ||
| if (numActs == randomIndex) { | ||
| targetActivity = activity; | ||
| break; | ||
| } | ||
| numActs++; | ||
| } | ||
| if (targetActivity != null) { | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| if (targetActivity == null) { | ||
| return unassignedJobs; | ||
| } | ||
| List<RelatednessToTourActivity> neighborActivities = new ArrayList<>(); | ||
| long maxTime = 0; | ||
| double maxDistance = 0; | ||
| for (VehicleRoute route : vehicleRoutes) { | ||
| for (TourActivity activity : route.getActivities()) { | ||
| if (activity == targetActivity) continue; | ||
| long absTime = Math.abs((long) targetActivity.getArrTime() - (long) activity.getArrTime()); | ||
| maxTime = Math.max(maxTime, absTime); | ||
| double distance = Math.abs(vrp.getTransportCosts().getDistance(targetActivity.getLocation(), activity.getLocation(), 0, route.getVehicle())); | ||
| maxDistance = Math.max(maxDistance, distance); | ||
| neighborActivities.add(new RelatednessToTourActivity(absTime, distance, activity, route)); | ||
| } | ||
| } | ||
| final double maxT = maxTime; | ||
| final double maxD = maxTime; | ||
| final double timeI = 10; | ||
| final double distanceI; | ||
| double distanceInfluence = 1; | ||
| if (random.nextDouble() < 0.5) { | ||
| distanceI = 0; | ||
| } else distanceI = distanceInfluence; | ||
| neighborActivities.sort((o1, o2) -> { | ||
| double rO1 = relatedness(o1, maxD, maxT, timeI, distanceI); | ||
| double rO2 = relatedness(o2, maxD, maxT, timeI, distanceI); | ||
| return Double.compare(rO1, rO2); | ||
| }); | ||
| int toRemove = getRuinShareFactory().createNumberToBeRemoved(); | ||
| for (RelatednessToTourActivity neighborActivity : neighborActivities) { | ||
| if (toRemove == 0) break; | ||
| Job j = ((TourActivity.JobActivity) neighborActivity.tourActivity).getJob(); | ||
| if (removeJob(j, neighborActivity.route)) { | ||
| unassignedJobs.add(j); | ||
| toRemove--; | ||
| } | ||
| } | ||
| return unassignedJobs; | ||
| } | ||
|
|
||
| private double relatedness(RelatednessToTourActivity o1, double maxDistance, double maxTime, double timeI, double distanceI) { | ||
| return timeI * o1.time / maxTime + distanceI * o1.distance / maxDistance; | ||
| } | ||
|
|
||
| @Override | ||
| public String toString() { | ||
| return "[name=timeRelatedRuin]"; | ||
| } | ||
|
|
||
| } |
80 changes: 80 additions & 0 deletions
80
...it-core/src/test/java/com/graphhopper/jsprit/core/algorithm/ruin/RuinTimeRelatedTest.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,80 @@ | ||
| /* | ||
| * Licensed to GraphHopper GmbH under one or more contributor | ||
| * license agreements. See the NOTICE file distributed with this work for | ||
| * additional information regarding copyright ownership. | ||
| * | ||
| * GraphHopper GmbH licenses this file to you under the Apache License, | ||
| * Version 2.0 (the "License"); you may not use this file except in | ||
| * compliance with the License. You may obtain a copy of the License at | ||
| * | ||
| * http://www.apache.org/licenses/LICENSE-2.0 | ||
| * | ||
| * Unless required by applicable law or agreed to in writing, software | ||
| * distributed under the License is distributed on an "AS IS" BASIS, | ||
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
| * See the License for the specific language governing permissions and | ||
| * limitations under the License. | ||
| */ | ||
|
|
||
| package com.graphhopper.jsprit.core.algorithm.ruin; | ||
|
|
||
| import com.graphhopper.jsprit.core.problem.Location; | ||
| import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem; | ||
| import com.graphhopper.jsprit.core.problem.job.Job; | ||
| import com.graphhopper.jsprit.core.problem.job.Service; | ||
| import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute; | ||
| import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity; | ||
| import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl; | ||
| import com.graphhopper.jsprit.core.util.RandomNumberGeneration; | ||
| import org.junit.Test; | ||
|
|
||
| import java.util.Arrays; | ||
| import java.util.Collection; | ||
| import java.util.Random; | ||
|
|
||
| /** | ||
| * Created by schroeder on 06/03/15. | ||
| */ | ||
| public class RuinTimeRelatedTest { | ||
|
|
||
| @Test | ||
| public void itShouldRuinTwoObviousClusters() { | ||
| Service s0 = Service.Builder.newInstance("s0").setLocation(Location.newInstance(9, 0)).build(); | ||
| Service s1 = Service.Builder.newInstance("s1").setLocation(Location.newInstance(9, 1)).build(); | ||
| Service s2 = Service.Builder.newInstance("s2").setLocation(Location.newInstance(9, 10)).build(); | ||
| Service s3 = Service.Builder.newInstance("s3").setLocation(Location.newInstance(9, 9)).build(); | ||
| Service s4 = Service.Builder.newInstance("s4").setLocation(Location.newInstance(9, 16)).build(); | ||
| Service s5 = Service.Builder.newInstance("s5").setLocation(Location.newInstance(9, 17)).build(); | ||
| Service s6 = Service.Builder.newInstance("s6").setLocation(Location.newInstance(9, 15.5)).build(); | ||
| Service s7 = Service.Builder.newInstance("s7").setLocation(Location.newInstance(9, 30)).build(); | ||
|
|
||
| VehicleImpl v = VehicleImpl.Builder.newInstance("v").setStartLocation(Location.newInstance(0, 0)).build(); | ||
|
|
||
| VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance().addJob(s1).addJob(s2) | ||
| .addJob(s6).addJob(s7).addJob(s0).addJob(s3).addJob(s4).addJob(s5).addVehicle(v).build(); | ||
|
|
||
| VehicleRoute vr1 = VehicleRoute.Builder.newInstance(v).addService(s0).addService(s1).addService(s2).addService(s3).setJobActivityFactory(vrp.getJobActivityFactory()).build(); | ||
| long time = 0; | ||
| for (TourActivity act : vr1.getActivities()) { | ||
| time += 2; | ||
| act.setArrTime(time); | ||
| } | ||
| VehicleRoute vr2 = VehicleRoute.Builder.newInstance(v) | ||
| .addService(s6).addService(s7).addService(s4).addService(s5).setJobActivityFactory(vrp.getJobActivityFactory()).build(); | ||
| time = 0; | ||
| for (TourActivity act : vr2.getActivities()) { | ||
| time += 2; | ||
| act.setArrTime(time); | ||
| } | ||
|
|
||
| RuinTimeRelated ruin = new RuinTimeRelated(vrp); | ||
|
|
||
| Random r = RandomNumberGeneration.newInstance(); | ||
| ruin.setRandom(r); | ||
| Collection<Job> ruined = ruin.ruinRoutes(Arrays.asList(vr1, vr2)); | ||
|
|
||
|
|
||
| } | ||
|
|
||
|
|
||
| } |