Skip to content

Commit eb78625

Browse files
author
Balázs Vissy
committed
graphhopper#354 - partial solution: adding new jobs as unassigned
1 parent c109fe6 commit eb78625

File tree

1 file changed

+57
-27
lines changed

1 file changed

+57
-27
lines changed

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

Lines changed: 57 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,14 @@
1717
*/
1818
package com.graphhopper.jsprit.core.algorithm;
1919

20+
import java.util.ArrayList;
21+
import java.util.Collection;
22+
import java.util.HashSet;
23+
import java.util.Set;
24+
25+
import org.slf4j.Logger;
26+
import org.slf4j.LoggerFactory;
27+
2028
import com.graphhopper.jsprit.core.algorithm.SearchStrategy.DiscoveredSolution;
2129
import com.graphhopper.jsprit.core.algorithm.listener.SearchStrategyListener;
2230
import com.graphhopper.jsprit.core.algorithm.listener.SearchStrategyModuleListener;
@@ -30,11 +38,6 @@
3038
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
3139
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
3240
import com.graphhopper.jsprit.core.util.Solutions;
33-
import org.slf4j.Logger;
34-
import org.slf4j.LoggerFactory;
35-
36-
import java.util.ArrayList;
37-
import java.util.Collection;
3841

3942

4043
/**
@@ -57,9 +60,8 @@ void addTermination(PrematureAlgorithmTermination termination) {
5760
@Override
5861
public boolean isPrematureBreak(DiscoveredSolution discoveredSolution) {
5962
for (PrematureAlgorithmTermination termination : terminationCriteria) {
60-
if (termination.isPrematureBreak(discoveredSolution)) {
63+
if (termination.isPrematureBreak(discoveredSolution))
6164
return true;
62-
}
6365
}
6466
return false;
6567
}
@@ -145,25 +147,41 @@ public void addInitialSolution(VehicleRoutingProblemSolution solution) {
145147
}
146148

147149
private void verify(VehicleRoutingProblemSolution solution) {
148-
int nuJobs = 0;
150+
Set<Job> allJobs = new HashSet<Job>(problem.getJobs().values());
151+
allJobs.removeAll(solution.getUnassignedJobs());
149152
for (VehicleRoute route : solution.getRoutes()) {
150-
nuJobs += route.getTourActivities().getJobs().size();
153+
allJobs.removeAll(route.getTourActivities().getJobs());
151154
if (route.getVehicle().getIndex() == 0)
152155
throw new IllegalStateException("vehicle used in initial solution has no index. probably a vehicle is used that has not been added to the " +
153-
" the VehicleRoutingProblem. only use vehicles that have already been added to the problem.");
156+
" the VehicleRoutingProblem. only use vehicles that have already been added to the problem.");
154157
for (TourActivity act : route.getActivities()) {
155-
if (act.getIndex() == 0) {
158+
if (act.getIndex() == 0)
156159
throw new IllegalStateException("act in initial solution has no index. activities are created and associated to their job in VehicleRoutingProblem\n." +
157-
" thus if you build vehicle-routes use the jobActivityFactory from vehicle routing problem like that \n" +
158-
" VehicleRoute.Builder.newInstance(knownVehicle).setJobActivityFactory(vrp.getJobActivityFactory).addService(..)....build() \n" +
159-
" then the activities that are created to build the route are identical to the ones used in VehicleRoutingProblem");
160-
}
160+
" thus if you build vehicle-routes use the jobActivityFactory from vehicle routing problem like that \n" +
161+
" VehicleRoute.Builder.newInstance(knownVehicle).setJobActivityFactory(vrp.getJobActivityFactory).addService(..)....build() \n" +
162+
" then the activities that are created to build the route are identical to the ones used in VehicleRoutingProblem");
161163
}
162164
}
163-
// if (nuJobs != problem.getJobs().values().size()) {
164-
// logger.warn("number of jobs in initial solution ({}) is not equal nuJobs in vehicle routing problem ({})" +
165-
// "\n this might yield unintended effects, e.g. initial solution cannot be improved anymore.", nuJobs, problem.getJobs().values().size());
166-
// }
165+
166+
solution.getUnassignedJobs().addAll(allJobs);
167+
168+
// Doesn't work
169+
// for (Vehicle v : problem.getVehicles()) {
170+
// boolean found = false;
171+
// for (VehicleRoute vr : solution.getRoutes())
172+
// if (vr.getVehicle().getId().equals(v.getId())) {
173+
// found = true;
174+
// break;
175+
// }
176+
// if (!found) {
177+
// solution.getRoutes().add(VehicleRoute.Builder.newInstance(v).build());
178+
// }
179+
// }
180+
181+
// if (nuJobs != problem.getJobs().values().size()) {
182+
// logger.warn("number of jobs in initial solution ({}) is not equal nuJobs in vehicle routing problem ({})" +
183+
// "\n this might yield unintended effects, e.g. initial solution cannot be improved anymore.", nuJobs, problem.getJobs().values().size());
184+
// }
167185
}
168186

169187
/**
@@ -214,15 +232,19 @@ public Collection<VehicleRoutingProblemSolution> searchSolutions() {
214232
Collection<VehicleRoutingProblemSolution> solutions = new ArrayList<VehicleRoutingProblemSolution>(initialSolutions);
215233
algorithmStarts(problem, solutions);
216234
bestEver = Solutions.bestOf(solutions);
217-
if (logger.isTraceEnabled()) log(solutions);
235+
if (logger.isTraceEnabled()) {
236+
log(solutions);
237+
}
218238
logger.info("iterations start");
219239
for (int i = 0; i < maxIterations; i++) {
220240
iterationStarts(i + 1, problem, solutions);
221241
logger.debug("start iteration: {}", i);
222242
counter.incCounter();
223243
SearchStrategy strategy = searchStrategyManager.getRandomStrategy();
224244
DiscoveredSolution discoveredSolution = strategy.run(problem, solutions);
225-
if (logger.isTraceEnabled()) log(discoveredSolution);
245+
if (logger.isTraceEnabled()) {
246+
log(discoveredSolution);
247+
}
226248
memorizeIfBestEver(discoveredSolution);
227249
selectedStrategy(discoveredSolution, problem, solutions);
228250
if (terminationManager.isPrematureBreak(discoveredSolution)) {
@@ -240,11 +262,15 @@ public Collection<VehicleRoutingProblemSolution> searchSolutions() {
240262
}
241263

242264
private void addBestEver(Collection<VehicleRoutingProblemSolution> solutions) {
243-
if (bestEver != null) solutions.add(bestEver);
265+
if (bestEver != null) {
266+
solutions.add(bestEver);
267+
}
244268
}
245269

246270
private void log(Collection<VehicleRoutingProblemSolution> solutions) {
247-
for (VehicleRoutingProblemSolution sol : solutions) log(sol);
271+
for (VehicleRoutingProblemSolution sol : solutions) {
272+
log(sol);
273+
}
248274
}
249275

250276
private void log(VehicleRoutingProblemSolution solution) {
@@ -277,9 +303,11 @@ private void log(DiscoveredSolution discoveredSolution) {
277303

278304
private void memorizeIfBestEver(DiscoveredSolution discoveredSolution) {
279305
if (discoveredSolution == null) return;
280-
if (bestEver == null) bestEver = discoveredSolution.getSolution();
281-
else if (discoveredSolution.getSolution().getCost() < bestEver.getCost())
306+
if (bestEver == null) {
307+
bestEver = discoveredSolution.getSolution();
308+
} else if (discoveredSolution.getSolution().getCost() < bestEver.getCost()) {
282309
bestEver = discoveredSolution.getSolution();
310+
}
283311
}
284312

285313

@@ -297,10 +325,12 @@ public VehicleRoutingAlgorithmListeners getAlgorithmListeners() {
297325

298326
public void addListener(VehicleRoutingAlgorithmListener l) {
299327
algoListeners.addListener(l);
300-
if (l instanceof SearchStrategyListener)
328+
if (l instanceof SearchStrategyListener) {
301329
searchStrategyManager.addSearchStrategyListener((SearchStrategyListener) l);
302-
if (l instanceof SearchStrategyModuleListener)
330+
}
331+
if (l instanceof SearchStrategyModuleListener) {
303332
searchStrategyManager.addSearchStrategyModuleListener((SearchStrategyModuleListener) l);
333+
}
304334
}
305335

306336
private void iterationEnds(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> solutions) {

0 commit comments

Comments
 (0)