Skip to content

Commit 82565b4

Browse files
oblonskioblonski
committed
add a way to use fast regret with custom contraints
1 parent ea1889b commit 82565b4

File tree

7 files changed

+359
-49
lines changed

7 files changed

+359
-49
lines changed

‎jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/box/Jsprit.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -436,6 +436,7 @@ public double makeNoise() {
436436
.build();
437437
scorer = getRegretScorer(vrp);
438438
regretInsertion.setScoringFunction(scorer);
439+
regretInsertion.setDependencyTypes(constraintManager.getDependencyTypes());
439440
regret = regretInsertion;
440441
}
441442
else {
@@ -461,6 +462,7 @@ public double makeNoise() {
461462
.build();
462463
scorer = getRegretScorer(vrp);
463464
regretInsertion.setScoringFunction(scorer);
465+
regretInsertion.setDependencyTypes(constraintManager.getDependencyTypes());
464466
regret = regretInsertion;
465467
}
466468
else{

‎jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/recreate/RegretInsertionConcurrentFast.java

Lines changed: 52 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
package com.graphhopper.jsprit.core.algorithm.recreate;
1919

2020
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
21+
import com.graphhopper.jsprit.core.problem.constraint.DependencyType;
2122
import com.graphhopper.jsprit.core.problem.job.Break;
2223
import com.graphhopper.jsprit.core.problem.job.Job;
2324
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
@@ -57,6 +58,8 @@ public class RegretInsertionConcurrentFast extends AbstractInsertionStrategy {
5758

5859
private boolean switchAllowed = true;
5960

61+
private DependencyType[] dependencyTypes = null;
62+
6063

6164
/**
6265
* Sets the scoring function.
@@ -97,6 +100,10 @@ private Set<String> getInitialVehicleIds(VehicleRoutingProblem vehicleRoutingPro
97100
return ids;
98101
}
99102

103+
public void setDependencyTypes(DependencyType[] dependencyTypes){
104+
this.dependencyTypes = dependencyTypes;
105+
}
106+
100107

101108
/**
102109
* Runs insertion.
@@ -139,15 +146,8 @@ public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> routes, Col
139146
List<Job> unassignedJobList = new ArrayList<Job>(jobs);
140147
List<Job> badJobList = new ArrayList<Job>();
141148
if(!firstRun && lastModified == null) throw new IllegalStateException("ho. this must not be.");
142-
if(firstRun){
143-
firstRun = false;
144-
updateInsertionData(priorityQueues, routes, unassignedJobList, updateRound);
145-
for(VehicleRoute r : routes) updates.put(r,updateRound);
146-
}
147-
else{
148-
updateInsertionData(priorityQueues, Arrays.asList(lastModified), unassignedJobList, updateRound);
149-
updates.put(lastModified,updateRound);
150-
}
149+
updateInsertionData(priorityQueues, routes, unassignedJobList, updateRound,firstRun,lastModified,updates);
150+
if(firstRun) firstRun = false;
151151
updateRound++;
152152
ScoredJob bestScoredJob = InsertionDataUpdater.getBest(switchAllowed,initialVehicleIds,fleetManager, insertionCostsCalculator, scoringFunction, priorityQueues, updates, unassignedJobList, badJobList);
153153
if (bestScoredJob != null) {
@@ -167,19 +167,38 @@ public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> routes, Col
167167
return badJobs;
168168
}
169169

170-
private void updateInsertionData(final TreeSet<VersionedInsertionData>[] priorityQueues, final Collection<VehicleRoute> routes, List<Job> unassignedJobList, final int updateRound) {
170+
private void updateInsertionData(final TreeSet<VersionedInsertionData>[] priorityQueues, final Collection<VehicleRoute> routes, List<Job> unassignedJobList, final int updateRound, final boolean firstRun, final VehicleRoute lastModified, Map<VehicleRoute, Integer> updates) {
171171
List<Callable<Boolean>> tasks = new ArrayList<Callable<Boolean>>();
172+
boolean updatedAllRoutes = false;
172173
for (final Job unassignedJob : unassignedJobList) {
173174
if(priorityQueues[unassignedJob.getIndex()] == null){
174175
priorityQueues[unassignedJob.getIndex()] = new TreeSet<VersionedInsertionData>(InsertionDataUpdater.getComparator());
175176
}
176177
final TreeSet<VersionedInsertionData> priorityQueue = priorityQueues[unassignedJob.getIndex()];
177-
tasks.add(new Callable<Boolean>() {
178-
@Override
179-
public Boolean call() throws Exception {
180-
return InsertionDataUpdater.update(switchAllowed,initialVehicleIds,fleetManager, insertionCostsCalculator, priorityQueue, updateRound, unassignedJob, routes);
178+
if(firstRun) {
179+
makeCallables(tasks, true, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes, lastModified);
180+
updatedAllRoutes = true;
181+
}
182+
else{
183+
if(dependencyTypes == null || dependencyTypes[unassignedJob.getIndex()] == null){
184+
makeCallables(tasks, false, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes, lastModified);
181185
}
182-
});
186+
else {
187+
DependencyType dependencyType = dependencyTypes[unassignedJob.getIndex()];
188+
if (dependencyType.equals(DependencyType.INTER_ROUTE) || dependencyType.equals(DependencyType.INTRA_ROUTE)) {
189+
makeCallables(tasks, false, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes, lastModified);
190+
updatedAllRoutes = true;
191+
} else {
192+
makeCallables(tasks, true, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes, lastModified);
193+
}
194+
}
195+
}
196+
}
197+
if(updatedAllRoutes){
198+
for(VehicleRoute r : routes) updates.put(r,updateRound);
199+
}
200+
else{
201+
updates.put(lastModified,updateRound);
183202
}
184203
try {
185204
List<Future<Boolean>> futures = executor.invokeAll(tasks);
@@ -189,8 +208,24 @@ public Boolean call() throws Exception {
189208
}
190209
}
191210

192-
193-
211+
private void makeCallables(List<Callable<Boolean>> tasks, boolean updateAll, final TreeSet<VersionedInsertionData> priorityQueue, final int updateRound, final Job unassignedJob, final Collection<VehicleRoute> routes, final VehicleRoute lastModified) {
212+
if(updateAll) {
213+
tasks.add(new Callable<Boolean>() {
214+
@Override
215+
public Boolean call() throws Exception {
216+
return InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueue, updateRound, unassignedJob, routes);
217+
}
218+
});
219+
}
220+
else {
221+
tasks.add(new Callable<Boolean>() {
222+
@Override
223+
public Boolean call() throws Exception {
224+
return InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueue, updateRound, unassignedJob, Arrays.asList(lastModified));
225+
}
226+
});
227+
}
228+
}
194229

195230

196231
}

‎jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/recreate/RegretInsertionFast.java

Lines changed: 51 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
package com.graphhopper.jsprit.core.algorithm.recreate;
1919

2020
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
21-
import com.graphhopper.jsprit.core.problem.job.Break;
21+
import com.graphhopper.jsprit.core.problem.constraint.DependencyType;
2222
import com.graphhopper.jsprit.core.problem.job.Job;
2323
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
2424
import com.graphhopper.jsprit.core.problem.vehicle.VehicleFleetManager;
@@ -51,7 +51,7 @@ public class RegretInsertionFast extends AbstractInsertionStrategy {
5151

5252
private boolean switchAllowed = true;
5353

54-
54+
private DependencyType[] dependencyTypes = null;
5555

5656
public RegretInsertionFast(JobInsertionCostsCalculator jobInsertionCalculator, VehicleRoutingProblem vehicleRoutingProblem, VehicleFleetManager fleetManager) {
5757
super(vehicleRoutingProblem);
@@ -78,6 +78,10 @@ public void setSwitchAllowed(boolean switchAllowed) {
7878
this.switchAllowed = switchAllowed;
7979
}
8080

81+
public void setDependencyTypes(DependencyType[] dependencyTypes){
82+
this.dependencyTypes = dependencyTypes;
83+
}
84+
8185
private Set<String> getInitialVehicleIds(VehicleRoutingProblem vehicleRoutingProblem) {
8286
Set<String> ids = new HashSet<String>();
8387
for(VehicleRoute r : vehicleRoutingProblem.getInitialVehicleRoutes()){
@@ -101,25 +105,25 @@ public String toString() {
101105
public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {
102106
List<Job> badJobs = new ArrayList<Job>(unassignedJobs.size());
103107

104-
Iterator<Job> jobIterator = unassignedJobs.iterator();
105-
while (jobIterator.hasNext()){
106-
Job job = jobIterator.next();
107-
if(job instanceof Break){
108-
VehicleRoute route = InsertionDataUpdater.findRoute(routes, job);
109-
if(route == null){
110-
badJobs.add(job);
111-
}
112-
else {
113-
InsertionData iData = insertionCostsCalculator.getInsertionData(route, job, NO_NEW_VEHICLE_YET, NO_NEW_DEPARTURE_TIME_YET, NO_NEW_DRIVER_YET, Double.MAX_VALUE);
114-
if (iData instanceof InsertionData.NoInsertionFound) {
115-
badJobs.add(job);
116-
} else {
117-
insertJob(job, iData, route);
118-
}
119-
}
120-
jobIterator.remove();
121-
}
122-
}
108+
// Iterator<Job> jobIterator = unassignedJobs.iterator();
109+
// while (jobIterator.hasNext()){
110+
// Job job = jobIterator.next();
111+
// if(job instanceof Break){
112+
// VehicleRoute route = InsertionDataUpdater.findRoute(routes, job);
113+
// if(route == null){
114+
// badJobs.add(job);
115+
// }
116+
// else {
117+
// InsertionData iData = insertionCostsCalculator.getInsertionData(route, job, NO_NEW_VEHICLE_YET, NO_NEW_DEPARTURE_TIME_YET, NO_NEW_DRIVER_YET, Double.MAX_VALUE);
118+
// if (iData instanceof InsertionData.NoInsertionFound) {
119+
// badJobs.add(job);
120+
// } else {
121+
// insertJob(job, iData, route);
122+
// }
123+
// }
124+
// jobIterator.remove();
125+
// }
126+
// }
123127

124128
List<Job> jobs = new ArrayList<Job>(unassignedJobs);
125129
TreeSet<VersionedInsertionData>[] priorityQueues = new TreeSet[vrp.getJobs().values().size() + 2];
@@ -130,15 +134,15 @@ public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> routes, Col
130134
while (!jobs.isEmpty()) {
131135
List<Job> unassignedJobList = new ArrayList<Job>(jobs);
132136
List<Job> badJobList = new ArrayList<Job>();
133-
if(!firstRun && lastModified == null) throw new IllegalStateException("fooo");
137+
if(!firstRun && lastModified == null) throw new IllegalStateException("last modified route is null. this should not be.");
134138
if(firstRun){
139+
updateInsertionData(priorityQueues, routes, unassignedJobList, updateRound, firstRun, lastModified, updates);
135140
firstRun = false;
136-
updateInsertionData(priorityQueues, routes, unassignedJobList, updateRound);
137-
for(VehicleRoute r : routes) updates.put(r,updateRound);
138141
}
139142
else{
140-
updateInsertionData(priorityQueues, Arrays.asList(lastModified), unassignedJobList, updateRound);
141-
updates.put(lastModified,updateRound);
143+
//update for all routes || remove history and only update modified route
144+
updateInsertionData(priorityQueues, routes, unassignedJobList, updateRound, firstRun, lastModified, updates);
145+
// updates.put(lastModified,updateRound);
142146
}
143147
updateRound++;
144148
ScoredJob bestScoredJob = InsertionDataUpdater.getBest(switchAllowed,initialVehicleIds,fleetManager,insertionCostsCalculator,scoringFunction,priorityQueues,updates,unassignedJobList,badJobList);
@@ -159,12 +163,31 @@ public Collection<Job> insertUnassignedJobs(Collection<VehicleRoute> routes, Col
159163
return badJobs;
160164
}
161165

162-
private void updateInsertionData(TreeSet<VersionedInsertionData>[] priorityQueues, Collection<VehicleRoute> routes, List<Job> unassignedJobList, int updateRound) {
166+
private void updateInsertionData(TreeSet<VersionedInsertionData>[] priorityQueues, Collection<VehicleRoute> routes, List<Job> unassignedJobList, int updateRound, boolean firstRun, VehicleRoute lastModified, Map<VehicleRoute, Integer> updates) {
163167
for (Job unassignedJob : unassignedJobList) {
164168
if(priorityQueues[unassignedJob.getIndex()] == null){
165169
priorityQueues[unassignedJob.getIndex()] = new TreeSet<VersionedInsertionData>(InsertionDataUpdater.getComparator());
166170
}
167-
InsertionDataUpdater.update(switchAllowed, initialVehicleIds,fleetManager,insertionCostsCalculator, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes);
171+
if(firstRun) {
172+
InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes);
173+
for(VehicleRoute r : routes) updates.put(r,updateRound);
174+
}
175+
else{
176+
if(dependencyTypes == null || dependencyTypes[unassignedJob.getIndex()] == null){
177+
InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, Arrays.asList(lastModified));
178+
for(VehicleRoute r : routes) updates.put(r,updateRound);
179+
}
180+
else {
181+
DependencyType dependencyType = dependencyTypes[unassignedJob.getIndex()];
182+
if (dependencyType.equals(DependencyType.INTER_ROUTE) || dependencyType.equals(DependencyType.INTRA_ROUTE)) {
183+
InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, routes);
184+
for(VehicleRoute r : routes) updates.put(r,updateRound);
185+
} else {
186+
InsertionDataUpdater.update(switchAllowed, initialVehicleIds, fleetManager, insertionCostsCalculator, priorityQueues[unassignedJob.getIndex()], updateRound, unassignedJob, Arrays.asList(lastModified));
187+
updates.put(lastModified,updateRound);
188+
}
189+
}
190+
}
168191
}
169192
}
170193

‎jsprit-core/src/main/java/com/graphhopper/jsprit/core/problem/constraint/ConstraintManager.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
package com.graphhopper.jsprit.core.problem.constraint;
1818

1919
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
20+
import com.graphhopper.jsprit.core.problem.job.Job;
2021
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
2122
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
2223
import com.graphhopper.jsprit.core.problem.solution.route.state.RouteAndActivityStateGetter;
@@ -59,17 +60,40 @@ public static enum Priority {
5960

6061
private boolean skillconstraintSet = false;
6162

63+
private final DependencyType[] dependencyTypes;
64+
6265
public ConstraintManager(VehicleRoutingProblem vrp, RouteAndActivityStateGetter stateManager) {
6366
this.vrp = vrp;
6467
this.stateManager = stateManager;
68+
dependencyTypes = new DependencyType[vrp.getJobs().size() + 1];
6569
}
6670

6771
public ConstraintManager(VehicleRoutingProblem vrp, RouteAndActivityStateGetter stateManager, Collection<Constraint> constraints) {
6872
this.vrp = vrp;
6973
this.stateManager = stateManager;
74+
dependencyTypes = new DependencyType[vrp.getJobs().size() + 1];
7075
resolveConstraints(constraints);
7176
}
7277

78+
public DependencyType[] getDependencyTypes() {
79+
return dependencyTypes;
80+
}
81+
82+
public void setDependencyType(String jobId, DependencyType dependencyType){
83+
Job job = vrp.getJobs().get(jobId);
84+
if(job != null) {
85+
dependencyTypes[job.getIndex()] = dependencyType;
86+
}
87+
}
88+
89+
public DependencyType getDependencyType(String jobId){
90+
Job job = vrp.getJobs().get(jobId);
91+
if(job != null){
92+
return dependencyTypes[job.getIndex()];
93+
}
94+
return DependencyType.NO_TYPE;
95+
}
96+
7397
private void resolveConstraints(Collection<Constraint> constraints) {
7498
for (Constraint c : constraints) {
7599
boolean constraintTypeKnown = false;

‎jsprit-core/src/main/java/com/graphhopper/jsprit/core/problem/constraint/DependencyType.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package com.graphhopper.jsprit.core.problem.constraint;
2+
3+
/**
4+
* Created by schroeder on 12/07/16.
5+
*/
6+
public enum DependencyType {
7+
8+
INTER_ROUTE, INTRA_ROUTE, NO_TYPE
9+
10+
}

0 commit comments

Comments
 (0)