OpenStreetMapを利用した車両ルーティング問題（VRP）のOptaPlanner解決例

[ トップ ] [ 編集 | 凍結 | 差分 | バックアップ | 添付 | リロード ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

OpenStreetMap?を利用した車両ルーティング問題（VRP）のOptaPlanner解決例 †

↑

システム構成 †

OptaPlanner: VRP ソルバー
OpenStreetMap? データ: 道路ネットワーク情報
GraphHopper?: OSM データを使用したルーティングエンジン

↑

実装手順 †

↑

1. OpenStreetMap? データの準備 †

対象地域の OSM データをダウンロードし、GraphHopper? 形式に変換します。

↑

2. ドメインモデルの拡張 †

車両と顧客の位置情報を地理座標で表現するようにモデルを拡張します。

public class Location {
    private double latitude;
    private double longitude;
    // getters and setters
}

public class Vehicle {
    private int id;
    private Location currentLocation;
    private List<Customer> route;
    // getters and setters
}

public class Customer {
    private int id;
    private Location location;
    private int demand;
    private TimeWindow timeWindow;
    // getters and setters
}

↑

3. GraphHopper? の統合 †

GraphHopper? を使用して、2 点間の実際の走行距離と時間を計算します。

public class RoutingService {
    private GraphHopper graphHopper;

    public RoutingService(String osmFile) {
        this.graphHopper = new GraphHopper().forServer();
        graphHopper.setOSMFile(osmFile);
        graphHopper.setGraphHopperLocation("./graph-cache");
        graphHopper.setEncodingManager(EncodingManager.create("car"));
        graphHopper.importOrLoad();
    }

    public GHResponse getRoute(Location from, Location to) {
        GHRequest req = new GHRequest(from.getLatitude(), from.getLongitude(),
                                      to.getLatitude(), to.getLongitude())
            .setVehicle("car");
        return graphHopper.route(req);
    }
}

↑

4. スコア計算の調整 †

実際の道路ネットワークに基づいた距離と時間を使用してスコアを計算します。

public class VehicleRoutingScoreCalculator implements EasyScoreCalculator<VehicleRoutingSolution> {
    private RoutingService routingService;

    @Override
    public Score calculateScore(VehicleRoutingSolution solution) {
        int hardScore = 0;
        int softScore = 0;

        for (Vehicle vehicle : solution.getVehicles()) {
            Location previousLocation = vehicle.getCurrentLocation();
            LocalTime currentTime = LocalTime.of(8, 0);

            for (Customer customer : vehicle.getRoute()) {
                GHResponse response = routingService.getRoute(previousLocation, customer.getLocation());
                long travelTimeInSeconds = response.getBest().getTime() / 1000;
                int distance = (int) response.getBest().getDistance();

                currentTime = currentTime.plusSeconds(travelTimeInSeconds);

                // 時間枠制約のチェック
                if (currentTime.isBefore(customer.getTimeWindow().getStart())) {
                    currentTime = customer.getTimeWindow().getStart();
                } else if (currentTime.isAfter(customer.getTimeWindow().getEnd())) {
                    hardScore -= MINUTES.between(customer.getTimeWindow().getEnd(), currentTime);
                }

                currentTime = currentTime.plusMinutes(15); // 配送時間
                softScore -= distance;

                previousLocation = customer.getLocation();
            }
        }

        return HardSoftScore.of(hardScore, softScore);
    }
}

↑

5. ソルバーの設定と実行 †

OptaPlanner のソルバーを設定し、問題を解きます。

public class VehicleRoutingApp {
    public static void main(String[] args) {
        SolverFactory<VehicleRoutingSolution> solverFactory = SolverFactory.createFromXmlResource("vehicleRoutingSolverConfig.xml");
        Solver<VehicleRoutingSolution> solver = solverFactory.buildSolver();

        VehicleRoutingSolution problem = createInitialSolution();
        VehicleRoutingSolution solution = solver.solve(problem);

        printSolution(solution);
    }

    private static VehicleRoutingSolution createInitialSolution() {
        // 初期解の作成ロジック
        // 車両と顧客の位置を実際の地理座標で設定
    }

    private static void printSolution(VehicleRoutingSolution solution) {
        // 解の出力ロジック
        // 各車両のルートを地理座標のリストとして出力
    }
}

↑