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) {
        // 解の出力ロジック
        // 各車両のルートを地理座標のリストとして出力
    }
}

結果の可視化

最適化されたルートを OpenStreetMap 上に表示することで、結果を視覚的に確認できます。これには、Leaflet.js などのJavaScript ライブラリを使用して、Web ブラウザ上で地図とルートを表示するインターフェースを作成します。

考察

このアプローチの利点:

実際の道路ネットワークに基づいた現実的なルーティング
交通規則（一方通行、転回禁止など）の自動的な考慮
より正確な走行距離と時間の見積もり

課題と改善点:

大規模な問題では計算時間が増加する可能性がある
リアルタイムの交通情報の統合
車両の種類による走行可能ルートの違いの考慮

まとめ

OpenStreetMap データと OptaPlanner を組み合わせることで、より現実的で精度の高い車両ルーティング問題の解決が可能になります。このアプローチは、実際の地理的制約を考慮したルート最適化を実現し、物流業界などでの実用的な応用が期待できます。