AStarLandmarks.java

Go to the documentation of this file.

/* *********************************************************************** *
 * project: org.matsim.*
 * AStarLandmarks.java
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 * copyright       : (C) 2007 by the members listed in the COPYING,        *
 *                   LICENSE and WARRANTY file.                            *
 * email           : info at matsim dot org                                *
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *   See also COPYING, LICENSE and WARRANTY file                           *
 *                                                                         *
 * *********************************************************************** */

package org.matsim.core.router;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.matsim.api.core.v01.network.Network;
import org.matsim.api.core.v01.network.Node;
import org.matsim.api.core.v01.population.Person;
import org.matsim.core.router.util.AStarNodeData;
import org.matsim.core.router.util.PreProcessLandmarks;
import org.matsim.core.router.util.TravelDisutility;
import org.matsim.core.router.util.TravelTime;
import org.matsim.core.utils.collections.RouterPriorityQueue;
import org.matsim.vehicles.Vehicle;

public class AStarLandmarks extends AStarEuclidean {

    protected int[] activeLandmarkIndexes;

    protected final Node[] landmarks;

    /*package*/ static final int controlInterval = 40;
    /*package*/ int controlCounter = 0;

    AStarLandmarks(final Network network, final PreProcessLandmarks preProcessData,
            final TravelDisutility costFunction, final TravelTime timeFunction) {
        this(network, preProcessData, costFunction, timeFunction, 1);
    }

    AStarLandmarks(final Network network, final PreProcessLandmarks preProcessData, final TravelTime timeFunction) {
        this(network, preProcessData, preProcessData.getCostFunction(), timeFunction, 1);
    }

    AStarLandmarks(final Network network, final PreProcessLandmarks preProcessData,
            final TravelDisutility costFunction, final TravelTime timeFunction, final double overdoFactor) {
        super(network, preProcessData, costFunction, timeFunction, overdoFactor);

        this.landmarks = preProcessData.getLandmarks();
    }

    @Override
    public Path calcLeastCostPath(final Node fromNode, final Node toNode, final double startTime, final Person person, final Vehicle vehicle) {
        this.controlCounter = 0;    // reset counter for each calculated path!
        
        if (this.landmarks.length >= 2) {
            initializeActiveLandmarks(fromNode, toNode, 2);
        } else {
            initializeActiveLandmarks(fromNode, toNode, this.landmarks.length);
        }
        return super.calcLeastCostPath(fromNode, toNode, startTime, person, vehicle);
    }

    @Override
    protected void relaxNode(final Node outNode, final Node toNode, final RouterPriorityQueue<Node> pendingNodes) {
        this.controlCounter++;
        if (this.controlCounter == controlInterval) {
            int newLandmarkIndex = checkToAddLandmark(outNode, toNode);
            if (newLandmarkIndex > 0) {
                updatePendingNodes(newLandmarkIndex, toNode, pendingNodes);
            }
            this.controlCounter = 0;
        }
        super.relaxNode(outNode, toNode, pendingNodes);
    }

    /*package*/ void initializeActiveLandmarks(final Node fromNode, final Node toNode, final int actLandmarkCount) {
        final PreProcessLandmarks.LandmarksData fromData = getPreProcessData(fromNode);
        final PreProcessLandmarks.LandmarksData toData = getPreProcessData(toNode);

        // Sort the landmarks according to the accuracy of their distance estimation they yield.
        double[] estTravelTimes = new double[actLandmarkCount];
        this.activeLandmarkIndexes = new int[actLandmarkCount];
        for (int i = 0; i < estTravelTimes.length; i++) {
            estTravelTimes[i] = Double.NEGATIVE_INFINITY;
        }
        double tmpTravTime;
        for (int i = 0; i < this.landmarks.length; i++) {
            tmpTravTime = estimateRemainingTravelCost(fromData, toData, i);
            for (int j = 0; j < estTravelTimes.length; j++) {
                if (tmpTravTime > estTravelTimes[j]) {
                    for (int k = estTravelTimes.length - 1; k > j; k--) {
                        estTravelTimes[k] = estTravelTimes[k - 1];
                        this.activeLandmarkIndexes[k] = this.activeLandmarkIndexes[k - 1];
                    }
                    estTravelTimes[j] = tmpTravTime;
                    this.activeLandmarkIndexes[j] = i;
                    break;
                }
            }
        }
    }

    @Override
    protected PreProcessLandmarks.LandmarksData getPreProcessData(final Node n) {
        return (PreProcessLandmarks.LandmarksData) super.getPreProcessData(n);
    }

    @Override
    protected double estimateRemainingTravelCost(final Node fromNode, final Node toNode) {

        PreProcessLandmarks.LandmarksData fromRole = getPreProcessData(fromNode);
        PreProcessLandmarks.LandmarksData toRole = getPreProcessData(toNode);
        double tmpTravCost;
        double travCost = 0;
        for (int i = 0, n = this.activeLandmarkIndexes.length; i < n; i++) {
            tmpTravCost = estimateRemainingTravelCost(fromRole, toRole, this.activeLandmarkIndexes[i]);
            if (tmpTravCost > travCost) {
                travCost = tmpTravCost;
            }
        }
        tmpTravCost = super.estimateRemainingTravelCost(fromNode, toNode);
        if (travCost > tmpTravCost) {
            return travCost;
        }
        /* else */
        return tmpTravCost;
    }

    /*package*/ void updatePendingNodes(final int newLandmarkIndex, final Node toNode, final RouterPriorityQueue<Node> pendingNodes) {
        Iterator<Node> it = pendingNodes.iterator();
        PreProcessLandmarks.LandmarksData toRole = getPreProcessData(toNode);
        List<Double> newEstRemTravCosts = new ArrayList<>();
        List<Node> nodesToBeUpdated = new ArrayList<>();
        while (it.hasNext()) {
            Node node = it.next();
            AStarNodeData data = getData(node);
            PreProcessLandmarks.LandmarksData ppRole = getPreProcessData(node);
            double estRemTravCost = data.getExpectedRemainingCost();
            double newEstRemTravCost = estimateRemainingTravelCost(ppRole, toRole, newLandmarkIndex);
            if (newEstRemTravCost > estRemTravCost) {
                nodesToBeUpdated.add(node);
                newEstRemTravCosts.add(newEstRemTravCost);
            }
        }
        for (Node node : nodesToBeUpdated) {
            pendingNodes.remove(node);
        }
        for (int i = 0; i < nodesToBeUpdated.size(); i++) {
            Node node = nodesToBeUpdated.get(i);
            AStarNodeData data = getData(node);
            data.setExpectedRemainingCost(newEstRemTravCosts.get(i));
            pendingNodes.add(node, getPriority(data));
        }
    }

    /*package*/ int checkToAddLandmark(final Node fromNode, final Node toNode) {
        double bestTravCostEst = estimateRemainingTravelCost(fromNode, toNode);
        PreProcessLandmarks.LandmarksData fromRole = getPreProcessData(fromNode);
        PreProcessLandmarks.LandmarksData toRole = getPreProcessData(toNode);
        int bestIndex = -1;
        for (int i = 0; i < this.landmarks.length; i++) {
            double tmpTravTime = estimateRemainingTravelCost(fromRole, toRole, i);
            if (tmpTravTime > bestTravCostEst) {
                bestIndex = i;
                bestTravCostEst = tmpTravTime;
            }
        }
        if (bestIndex != -1) {
            int[] newActiveLandmarks = new int[this.activeLandmarkIndexes.length + 1];
            System.arraycopy(this.activeLandmarkIndexes, 0, newActiveLandmarks, 0, this.activeLandmarkIndexes.length);
            newActiveLandmarks[this.activeLandmarkIndexes.length] = bestIndex;
            this.activeLandmarkIndexes = newActiveLandmarks;
        }
        return bestIndex;
    }

    protected double estimateRemainingTravelCost(final PreProcessLandmarks.LandmarksData fromRole,
            final PreProcessLandmarks.LandmarksData toRole, final int index) {
        double tmpTravTime;
        final double fromMinLandmarkTravelTime = fromRole.getMinLandmarkTravelTime(index);
        final double toMaxLandmarkTravelTime = toRole.getMaxLandmarkTravelTime(index);
        tmpTravTime = fromMinLandmarkTravelTime - toMaxLandmarkTravelTime;
        if (tmpTravTime < 0) {
            tmpTravTime = toRole.getMinLandmarkTravelTime(index) - fromRole.getMaxLandmarkTravelTime(index);
            if (tmpTravTime <= 0) {
                return 0;
            }
        }
        return tmpTravTime * this.overdoFactor;
    }
}