私は JSprit を使用して、タイム ウィンドウを使用した複数の巡回セールスマンの問題を解決しています。時間の制約があるため、1 週間に 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);}
}
決まった仕事の日を変更すると、その日に割り当てられた車両は常に満員で、仕事が割り当てられないことに気付きました。