using System;
using System.Collections.Generic;
using System.Linq;
public class Customer
{
public int Id { get; set; }
public int X { get; set; }
public int Y { get; set; }
public int Demand { get; set; }
}
public class VRPProblem
{
public List<Customer> Customers { get; set; } = new List<Customer>();
public double[,] DistanceMatrix { get; set; }
public double[,] Tau { get; set; }
public int VehicleCapacity { get; set; } = 200;
public void CalculateDistanceMatrix()
{
int n = Customers.Count;
DistanceMatrix = new double[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
double dx = Customers[i].X - Customers[j].X;
double dy = Customers[i].Y - Customers[j].Y;
DistanceMatrix[i, j] = Math.Sqrt(dx * dx + dy * dy);
}
}
}
}
public class Ant
{
private static readonly Random Random = new Random();
public List<List<int>> Routes { get; set; } = new List<List<int>>();
public double TotalDistance { get; set; }
public void ConstructSolution(VRPProblem problem, double[,] tau, double alpha, double beta)
{
int depotId = 0;
var customers = problem.Customers;
var unvisited = new HashSet<int>(customers.Where(c => c.Id != depotId).Select(c => c.Id));
Routes.Clear();
TotalDistance = 0;
while (unvisited.Count > 0)
{
var currentRoute = new List<int> { depotId };
int currentLoad = 0;
var available = unvisited.Where(c => customers[c].Demand <= problem.VehicleCapacity).ToList();
if (available.Count == 0) break;
int nextCustomer = SelectNextCustomer(depotId, available, tau, alpha, beta, problem.DistanceMatrix);
currentRoute.Add(nextCustomer);
currentLoad += customers[nextCustomer].Demand;
unvisited.Remove(nextCustomer);
while (true)
{
int lastPos = currentRoute.Last();
available = unvisited.Where(c => customers[c].Demand <= (problem.VehicleCapacity - currentLoad)).ToList();
if (available.Count == 0) break;
nextCustomer = SelectNextCustomer(lastPos, available, tau, alpha, beta, problem.DistanceMatrix);
currentRoute.Add(nextCustomer);
currentLoad += customers[nextCustomer].Demand;
unvisited.Remove(nextCustomer);
}
currentRoute.Add(depotId);
Routes.Add(currentRoute);
double routeDistance = 0;
for (int i = 0; i < currentRoute.Count - 1; i++)
{
int from = currentRoute[i];
int to = currentRoute[i + 1];
routeDistance += problem.DistanceMatrix[from, to];
}
TotalDistance += routeDistance;
}
}
private int SelectNextCustomer(int currentPos, List<int> candidates, double[,] tau, double alpha, double beta, double[,] distance)
{
double[] probabilities = new double[candidates.Count];
double total = 0;
for (int i = 0; i < candidates.Count; i++)
{
int j = candidates[i];
double pheromone = tau[currentPos, j];
double eta = 1.0 / distance[currentPos, j];
probabilities[i] = Math.Pow(pheromone, alpha) * Math.Pow(eta, beta);
total += probabilities[i];
}
if (total == 0) return candidates[Random.Next(candidates.Count)];
double rand = Random.NextDouble() * total;
double sum = 0;
for (int i = 0; i < probabilities.Length; i++)
{
sum += probabilities[i];
if (sum >= rand) return candidates[i];
}
return candidates.Last();
}
}
public class ACO
{
public VRPProblem Problem { get; set; }
public int NumberOfAnts { get; set; } = 20;
public int MaxIterations { get; set; } = 100;
public double Alpha { get; set; } = 1;
public double Beta { get; set; } = 3;
public double Rho { get; set; } = 0.1;
public double Q { get; set; } = 100;
public (List<List<int>> Routes, double Distance) Solve()
{
int n = Problem.Customers.Count;
Problem.Tau = new double[n, n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
Problem.Tau[i, j] = 1.0;
List<List<int>> bestRoutes = null;
double bestDistance = double.MaxValue;
for (int iter = 0; iter < MaxIterations; iter++)
{
var ants = new List<Ant>();
for (int k = 0; k < NumberOfAnts; k++)
{
var ant = new Ant();
ant.ConstructSolution(Problem, Problem.Tau, Alpha, Beta);
ants.Add(ant);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
Problem.Tau[i, j] *= (1 - Rho);
foreach (var ant in ants)
{
if (ant.TotalDistance == 0) continue;
double contribution = Q / ant.TotalDistance;
foreach (var route in ant.Routes)
{
for (int i = 0; i < route.Count - 1; i++)
{
int from = route[i];
int to = route[i + 1];
Problem.Tau[from, to] += contribution;
Problem.Tau[to, from] += contribution;
}
}
}
var currentBest = ants.OrderBy(a => a.TotalDistance).First();
if (currentBest.TotalDistance < bestDistance)
{
bestDistance = currentBest.TotalDistance;
bestRoutes = currentBest.Routes;
}
}
return (bestRoutes, bestDistance);
}
}
public class Program
{
public static void Main()
{
var problem = new VRPProblem();
problem.Customers = new List<Customer>
{
new Customer { Id = 0, X = 40, Y = 50, Demand = 0 },
new Customer { Id = 1, X = 45, Y = 68, Demand = 10 },
new Customer { Id = 2, X = 45, Y = 70, Demand = 30 },
new Customer { Id = 3, X = 42, Y = 66, Demand = 10 },
new Customer { Id = 4, X = 42, Y = 68, Demand = 10 },
new Customer { Id = 5, X = 42, Y = 60, Demand = 10 },
new Customer { Id = 6, X = 40, Y = 69, Demand = 20 },
new Customer { Id = 7, X = 40, Y = 66, Demand = 20 },
new Customer { Id = 8, X = 38, Y = 68, Demand = 20 },
new Customer { Id = 9, X = 38, Y = 70, Demand = 10 },
new Customer { Id = 10, X = 35, Y = 66, Demand = 10 },
new Customer { Id = 11, X = 35, Y = 69, Demand = 10 },
new Customer { Id = 12, X = 25, Y = 85, Demand = 20 },
new Customer { Id = 13, X = 22, Y = 75, Demand = 30 },
new Customer { Id = 14, X = 22, Y = 85, Demand = 10 },
new Customer { Id = 15, X = 20, Y = 80, Demand = 40 },
new Customer { Id = 16, X = 20, Y = 85, Demand = 40 },
new Customer { Id = 17, X = 18, Y = 75, Demand = 20 },
new Customer { Id = 18, X = 15, Y = 75, Demand = 20 },
new Customer { Id = 19, X = 15, Y = 80, Demand = 10 },
new Customer { Id = 20, X = 30, Y = 50, Demand = 10 }