我正在使用 JSprit 解决具有时间窗的多旅行推销员问题：我有一个推销员必须在一周内尽可能快地访问 n 个客户，但时间有限。我为每一天配置了一辆车，为每个客户配置了一项服务。
它实际上正在工作，但我找不到处理在特定时间计划的工作的方法。例如，一位推销员有 15 个客户要见，但在星期一下午 3 点，他安排了一个约会。考虑到该约束，我希望优化路线。
我试图指定一个时间窗口与约会相对应的工作，但通常没有分配工作，而仍有车辆可用！我试图将所需的技能放在工作和与正确日期相关的车辆上，并获得相同的结果。
所以这是我的问题： - 我不能在特定时间将工作设置为强制性（不能不分配）。- 我不明白为什么有未使用的车辆而有未分配的工作。
编辑：我修改我的代码以添加优先级并扩大时间窗口作为建议。不走运，作业 1 仍未分配。
public class test {
private ArrayList<Service> serviceList; // list of services
private ArrayList<Location> locationList; // list of location
private Location dep; // departure & arrival for each day
private String parameters;
// distances between locations
private double times[][];
public test()
{
this.serviceList = new ArrayList<>();
this.locationList = new ArrayList<>();
this.parameters = "";
}
public void test(int nb)
{
this.times = new double[nb+1][nb+1];
// collect data from json for the list of geocoded services
try (InputStream in = new ByteArrayInputStream(json.getBytes(StandardCharsets.UTF_8));
JsonReader read = javax.json.Json.createReader(in)) {
JsonObject obj = read.readObject();
JsonArray results = obj.getJsonArray("clients");
// departure
dep = Location.Builder.newInstance().setId("0").setIndex(0).setCoordinate(Coordinate.newInstance(48.88626, 2.22135)).build();
// parameters for OSRM request
parameters = "&loc=48.88626, 2.22135";
locationList.add(dep);
// get locations from json
for(int i=0; i<nb;i++)
{
JsonObject result = results.getValuesAs(JsonObject.class).get(i);
Location l = Location.Builder.newInstance().setId(Integer.toString(i+1)).setIndex(i+1).setCoordinate(Coordinate.newInstance(Double.valueOf(result.getString("latitude")), Double.valueOf(result.getString("longitude")))).build();
locationList.add(l);
// parameters for OSRM request
parameters += "&loc="+result.getString("latitude")+","+result.getString("longitude");
}
// Vehicles
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType");
VehicleType vehicleType = vehicleTypeBuilder.setCostPerTransportTime(1).setCostPerWaitingTime(1).setCostPerServiceTime(1).setCostPerDistance(0).build();
// vehicule for each day
VehicleImpl vehicleMon = VehicleImpl.Builder.newInstance("vehicleMon").setType(vehicleType).setStartLocation(dep).setEarliestStart(32400).setLatestArrival(64800).build();
VehicleImpl vehicleTue = VehicleImpl.Builder.newInstance("vehicleTue").setType(vehicleType).setStartLocation(dep).setEarliestStart(118800).setLatestArrival(151200).build();
VehicleImpl vehicleWed = VehicleImpl.Builder.newInstance("vehicleWed").setType(vehicleType).setStartLocation(dep).setEarliestStart(205200).setLatestArrival(237600).build();
VehicleImpl vehicleThu = VehicleImpl.Builder.newInstance("vehicleThu").setType(vehicleType).setStartLocation(dep).setEarliestStart(291600).setLatestArrival(324000).build();
VehicleImpl vehicleFry = VehicleImpl.Builder.newInstance("vehicleFry").setType(vehicleType).setStartLocation(dep).setEarliestStart(378000).setLatestArrival(410400).build();
VehicleImpl vehicleSat = VehicleImpl.Builder.newInstance("vehicleSat").setType(vehicleType).setStartLocation(dep).setEarliestStart(464400).setLatestArrival(496800).build();
VehicleImpl vehicleSun = VehicleImpl.Builder.newInstance("vehicleSun").setType(vehicleType).setStartLocation(dep).setEarliestStart(550800).setLatestArrival(583200).build();
// the job with a specific time window which represent a scheduled appointment
Service serviceTW = Service.Builder.newInstance(Integer.toString(1))
.setName("1")
.addTimeWindow(124200, 131400) // 2 hours window
.setPriority(1) // high priority
.setServiceTime(3600).setLocation(locationList.get(1)).build();
serviceList.add(serviceTW);
// jobs
for(int i=1; i<nb; i++) // we skip the first one which is above
{
Service service = Service.Builder.newInstance(Integer.toString(i+1))
.setName(Integer.toString(i+1))
.setPriority(3) // low priority
.addTimeWindow(32400, 583200) // time window for all week
.setServiceTime(3600).setLocation(locationList.get(i+1)).build();
serviceList.add(service);
}
// matrix time
// retrieve traveling time from OSRM
getOSRM_times();
VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
for(int i=0; i<nb ;i++)
{
for(int j=0; j<nb+1;j++)
{
costMatrixBuilder.addTransportTime(Integer.toString(i), Integer.toString(j), times[i][j]/10);
}
}
// adding vehicles
VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder
.addVehicle(vehicleMon)
.addVehicle(vehicleTue)
.addVehicle(vehicleWed)
.addVehicle(vehicleThu)
.addVehicle(vehicleFry)
.addVehicle(vehicleSat)
.addVehicle(vehicleSun)
.addAllJobs(serviceList).setFleetSize(FleetSize.FINITE).setRoutingCost(costMatrix);
// Problem/Solution
VehicleRoutingProblem problem = vrpBuilder.build();
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
File dir = new File("output");
// if the directory does not exist, create it
if (!dir.exists()){
System.out.println("creating directory ./output");
boolean result = dir.mkdir();
if(result) System.out.println("./output created");
}
// RESULTS
//xml
new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");
// console
SolutionPrinter.print(problem, bestSolution, Print.VERBOSE);
// image
new Plotter(problem,bestSolution).setLabel(Plotter.Label.ID).plot("output/solution.png", "solution");
}catch (IOException ex) {Logger.getLogger(Json.class.getName()).log(Level.SEVERE, null, ex);}
}
我注意到，如果我改变了我固定工作的日期，分配给这一天的车辆将永远是满的，而工作是未分配的。