Hi all I need to print the fully details of the solution from google or tools
What I mean that I have a distance matrix (CSV) with multiple locations So when I got the solution, I need to determine the actual locations for the optimization solution.
I need to extract the actual location because I need to determine by mechanism the Lng & Lat of this location.
Here is my code:
public class OptimizationService
{
private readonly Dictionary<long, long> idx = new();
public static void VRP(DataModel data)
{
var locations = new List<Location>();
// Build depots; consider start and end depot the same for now
var vehicles = data.Vehicles.Take(1).ToList();
var capacities = new long[vehicles.Count];
AddIndex(vehicles[0].StartDepot.Location, locations);
for (int i = 0; i < vehicles.Count; i++)
{
capacities[i] = vehicles[i].WeightCapacity;
}
// Build pickups and deliveries with time windows; assign times for depot (zero index)
var passengers = data.Passengers.Take(10).ToList();
var timeWindows = new long[passengers.Count * 2 + 1, 2];
timeWindows[0, 0] = vehicles[0].StartDepot.Time.ToUnixTimeSeconds(); //TODO: adjust problem
timeWindows[0, 1] = vehicles[0].EndDepot.Time.ToUnixTimeSeconds();//TODO: adjust problem
var minTime = timeWindows[0, 0];
var maxTime = timeWindows[0, 1];
var demands = new long[passengers.Count * 2 + 1];
var pickupsDeliveries = new int[passengers.Count][];
var serviceTimes = new long[passengers.Count * 2 + 1];
for (int i = 0; i < passengers.Count; i++)
{
var passenger = passengers[i];
// Build pickup and delivery
var pickupIndex = AddIndex(passenger.PickupLocation, locations);
var deliveryIndex = AddIndex(passenger.DropOffLocation, locations);
pickupsDeliveries[i] = [pickupIndex, deliveryIndex];
// Build demand; capacity will be increased or decreased based on node index
demands[pickupIndex] = passenger.Demand;
demands[deliveryIndex] = -passenger.Demand;
//TODO: adjust problem
passenger.PickupDueTime = null;
passenger.DropOffReadyTime = null;
// Build time window
timeWindows[pickupIndex, 0] = passenger.PickupReadyTime.ToUnixTimeSeconds(minTime);
timeWindows[pickupIndex, 1] = passenger.PickupDueTime.ToUnixTimeSeconds(maxTime);
timeWindows[deliveryIndex, 0] = passenger.DropOffReadyTime.ToUnixTimeSeconds(minTime);
timeWindows[deliveryIndex, 1] = passenger.DropOffDueTime.ToUnixTimeSeconds(maxTime);
// Build service time; should not exceed 1 minute
var serviceTime = Math.Min(passenger.Demand * 10, 60);
serviceTimes[pickupIndex] = serviceTime;
serviceTimes[deliveryIndex] = serviceTime;
}
// Build routing problem
var manager = new RoutingIndexManager(locations.Count, vehicles.Count, 0);
var routing = new RoutingModel(manager);
// Build distance and time matrix
(long[,] distanceMatrix, long[,] timeMatrix) = CalculateDistanceAndTimeMatrix(locations, out var validationErrors);
// Create distance constraint
var distanceDimension = AddDistanceConstraint(routing, manager, distanceMatrix);
// Create capacity constraint
var capacityDimension = AddCapacityConstraint(routing, manager, capacities, demands);
// Create time constraint
var timeDimension = AddTimeWindowConstraint(routing, manager, timeMatrix, timeWindows, serviceTimes, vehicles.Count);
// Define Transportation Requests.
AddPickupsAndDeliveries(routing, manager, distanceDimension, pickupsDeliveries);
RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
searchParameters.TimeLimit = new Duration() { Seconds = 5 };
Assignment solution = routing.SolveWithParameters(searchParameters);
solution.
if (solution is not null)
{
PrintSolution(routing, manager, solution, vehicles.Count);
}
else
{
//return null;
}
}
static RoutingDimension AddDistanceConstraint(RoutingModel routing, RoutingIndexManager manager, long[,] distanceMatrix)
{
// Create and register a distance transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return distanceMatrix[fromNode, toNode];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Distance constraint; capacity represents the max route distance
// Multiply distance constraint by 100 to minimize distance as much as we can
routing.AddDimension(transitCallbackIndex, 0, 500_000, true, "Distance");
RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
distanceDimension.SetGlobalSpanCostCoefficient(100);
return distanceDimension;
}
static RoutingDimension AddCapacityConstraint(RoutingModel routing, RoutingIndexManager manager, long[] capacities, long[] demands)
{
// Create and register a capacity transit callback.
int transitCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
{
var fromNode = manager.IndexToNode(fromIndex);
return demands[fromNode];
});
// Set capacity dimension
routing.AddDimensionWithVehicleCapacity(transitCallbackIndex, 0, capacities, true, "Capacity");
RoutingDimension capacityDimension = routing.GetMutableDimension("Capacity");
return capacityDimension;
}
static RoutingDimension AddTimeWindowConstraint(RoutingModel routing, RoutingIndexManager manager, long[,] timeMatrix, long[,] timeWindows, long[] serviceTimes, int vehicleCount)
{
// Create and register a time transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to time matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return serviceTimes[fromNode] + timeMatrix[fromNode, toNode];
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Time constraint: slack max represents the max waiting time in seconds
// while capacity represents total route time in seconds
routing.AddDimension(transitCallbackIndex, 1800, long.MaxValue, false, "Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < timeWindows.GetLength(0); ++i)
{
long index = manager.NodeToIndex(i);
timeDimension.CumulVar(index).SetRange(timeWindows[i, 0], timeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < vehicleCount; ++i)
{
long index = routing.Start(i);
timeDimension.CumulVar(index).SetRange(timeWindows[0, 0], timeWindows[0, 1]);
}
// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < vehicleCount; ++i)
{
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
}
return timeDimension;
}
static void AddPickupsAndDeliveries(RoutingModel routing, RoutingIndexManager manager, RoutingDimension distanceDimension, int[][] pickupsDeliveries)
{
var solver = routing.solver();
for (int i = 0; i < pickupsDeliveries.GetLength(0); i++)
{
var pickupIndex = manager.NodeToIndex(pickupsDeliveries[i][0]);
var deliveryIndex = manager.NodeToIndex(pickupsDeliveries[i][1]);
routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex)));
solver.Add(solver.MakeLessOrEqual(distanceDimension.CumulVar(pickupIndex),
distanceDimension.CumulVar(deliveryIndex)));
}
}
static (long[,], long[,]) CalculateDistanceAndTimeMatrix(List<Location> locations, out List<string> validationErrors)
{
var csvFilePath = "distance_matrix.csv";
var locationDic = locations.DistinctBy(l => l.Address).ToDictionary(l => l.Address, l => l);
// Build temporary distance matrix since locations can be duplicated but with difference indexes
var headerRowRead = false;
var headerNames = new List<string>();
var matrixDic = new Dictionary<(string From, string To), (long Distance, long Duration)>();
using (var reader = new StreamReader(csvFilePath))
{
using var csv = new CsvReader(reader, CultureInfo.InvariantCulture);
string fieldValue;
while (csv.Read())
{
// Read header data and cache location names
if (!headerRowRead)
{
for (int col = 1; csv.TryGetField(col, out fieldValue); col++)
{
headerNames.Add(fieldValue.Trim().ToLower());
}
headerRowRead = true;
continue;
}
var fromAddress = string.Empty;
for (int col = 0; csv.TryGetField(col, out fieldValue); col++)
{
fieldValue = fieldValue.Trim().ToLower();
if (col == 0)
{
if (!locationDic.TryGetValue(fieldValue, out var from))
{
break;
}
fromAddress = from.Address.Trim().ToLower();
}
else if (locationDic.TryGetValue(headerNames[col - 1], out var to))
{
var toAddress = to.Address.Trim().ToLower();
if (matrixDic.ContainsKey((fromAddress, toAddress)))
{
continue;
}
var matrixValues = fieldValue.Split(';');
matrixDic.Add(
(fromAddress, toAddress),
(long.Parse(matrixValues.ElementAt(0)), long.Parse(matrixValues.ElementAt(1))));
}
}
// Reset from address
fromAddress = string.Empty;
}
}
// Build the actual distance matrix
var counter = 0;
var distanceMatrix = new List<(int Row, List<long> Columns)>();
var durationMatrix = new List<(int Row, List<long> Columns)>();
var locationAddresses = locations.Select(l => l.Address).ToList();
foreach (var from in locationAddresses)
{
var distanceCols = new List<long>();
var durationCols = new List<long>();
foreach (var to in locationAddresses)
{
(long distance, long duration) = matrixDic[(from, to)];
distanceCols.Add(distance);
durationCols.Add(duration);
}
distanceMatrix.Add((counter, distanceCols));
durationMatrix.Add((counter, durationCols));
}
//TODO: Ignore case
validationErrors = locations.Where(l => !headerNames.Contains(l.Address)).Select(l => l.Address).ToList();
return (Create2dMatrix(distanceMatrix), Create2dMatrix(durationMatrix));
}
static int AddIndex(Location location, List<Location> list)
{
location.Address = location.Address.Trim().ToLower();
list.Add(location);
return list.Count - 1;
}
static long[,] Create2dMatrix(List<(int Row, List<long> Columns)> matrix)
{
var rowCount = matrix.Count;
var columnCount = matrix[0].Columns.Count;
long[,] matrix2d = new long[rowCount, columnCount];
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < columnCount; j++)
{
matrix2d[i, j] = matrix[i].Columns[j];
}
}
return matrix2d;
}
static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution, in int count)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Display dropped nodes.
string droppedNodes = "Dropped nodes:";
for (int index = 0; index < routing.Size(); ++index)
{
if (routing.IsStart(index) || routing.IsEnd(index))
{
continue;
}
if (solution.Value(routing.NextVar(index)) == index)
{
droppedNodes += " " + manager.IndexToNode(index);
}
}
// Inspect solution.
long totalDistance = 0;
for (int i = 0; i < count; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
Console.Write("[{0},{1}] -> ", previousIndex , manager.IndexToNode((int)index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
}
Console.WriteLine("Total Distance of all routes: {0}m", totalDistance);
}
}
public static class DateTimeExtensions
{
public static long ToUnixTimeSeconds(this DateTime datetime)
{
datetime = DateTime.SpecifyKind(datetime, DateTimeKind.Local);
DateTimeOffset dateTimeOffset = datetime;
return dateTimeOffset.ToUnixTimeSeconds();
}
public static long ToUnixTimeSeconds(this DateTime? datetime, long fallback)
{
if (datetime is null)
{
return fallback;
}
return datetime.Value.ToUnixTimeSeconds();
}
}
So, How I can solve it?
Thank all.
How did you build the distance matrix ?
I do not think that reversing the distance matrix to get coordinates is possible or well defined.
If you look at the code samples, they use IndexToNode and other methods to get the nodes from the solution.