Business Objects & Instantiation
Visualization
The image below visualizes the data created above. In this example we have five cities and ten edges. We want to know the optimal tour, which has to be determined by the solver according to the constraints in the model we will define in the following step.
Node (Business Object)
Each node holds its own name and information about whether it is a depot or not.
This is important for the implementation as some constraints are restricted to the depot or only customers.
Node.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace VRP
{
/// <summary>
/// A node of the Multi Vehicle Routing Problem /w Capacity Constraints
/// </summary>
public class Node : INode
{
/// <summary>
/// Initializes a new instance of the
/// <see cref="Node"/> class, representing a node of the tsp
/// </summary>
/// <param name="name">
/// Name of the node
/// </param>
/// <param name="demand">
/// The demand of this node; A negative demand is supply
/// </param>
/// <param name"isDepot">
/// Indicator if this node is a depot or not
/// </param>
public Node(string name, double demand, bool isDepot)
{
this.Name = name;
this.Demand = demand;
this.IsDepot = isDepot;
}
/// <summary>
/// Gets or sets a value indicating whether the node is a depot
/// </summary>
public bool IsDepot { get; set; }
/// <summary>
/// Gets the demand of this node; The depot has no demand but "infinite" supply
/// </summary>
public double Demand { get; }
/// <summary>
/// Gets the name of the node
/// </summary>
public string Name { get; }
/// <summary>
/// Name of the node
/// </summary>
/// <returns>
/// The name of this node (<see cref="string"/>).
/// </returns>
public override string ToString() => this.Name;
}
}
Edge (Business Object)
An Edge connects exactly two nodes while having a fixed cost for traveling that edge.
Edge.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace VRP
{
/// <summary>
/// An edge between two nodes of the Multi Vehicle Routing Problem /w Capacity Constraints
/// </summary>
public class Edge : IEdge
{
/// <summary>
/// Initializes a new instance of the <see cref="Edge"/> class
/// </summary>
/// <param name="fromNode">
/// The departing node
/// </param>
/// <param name="toNode">
/// The arrival node
/// </param>
/// <param name="transportationCost">
/// The length of the edge
/// </param>
public Edge(INode fromNode, INode toNode, double? transportationCost)
{
// set the parameter information
this.FromNode = fromNode;
this.ToNode = toNode;
this.transportationCost = transportationCost;
}
/// <summary>
/// Gets the capacity of the edge
/// </summary>
public double? transportationCost { get; }
/// <summary>
/// Gets the end node of the edge
/// </summary>
public INode ToNode { get; }
/// <summary>
/// Gets the start node of the edge
/// </summary>
public INode FromNode { get; }
/// <summary>
/// Gets or sets a value indicating whether the edge is used in the solution
/// </summary>
public bool IsUsed { get; set; }
/// <summary>
/// Name of the edge
/// </summary>
/// <returns>
/// The <see cref="string"/>.
/// </returns>
public override string ToString() => $"Edge {this.FromNode} to {this.ToNode}";
}
}
Program instance
Instantiation of the different Nodes and Edges, the Model, as well as the Solver and an empty Solution.
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace VRP
{
using System.Configuration;
using OPTANO.Modeling.Common;
using OPTANO.Modeling.Optimization;
using OPTANO.Modeling.Optimization.Configuration;
using OPTANO.Modeling.Optimization.Solver.Gurobi810;
/// <summary>
/// Demo program solving a vehicle routing problem
/// </summary>
class Program
{
/// <summary>
/// The main method
/// </summary>
/// <param name="args">
/// no arguments required
/// </param>
static void Main(string[] args)
{
INode pad = new Node("Paderborn", 0, true); // Starting node (depot)
// of our vehicle routing problem
INode nyc = new Node("New York", 1500, false);
INode bjs = new Node("Beijing", 2000, false);
INode sao = new Node("São Paulo", 2000, false);
INode sfo = new Node("San Francisco", 2500, false);
var nodes = new List<INode> { pad, nyc, bjs, sao, sfo };
var edges = new List<IEdge>
{
//Paderborn outgoing
new Edge(pad, nyc, 6130),
new Edge(pad, bjs, 7660),
new Edge(pad, sao, 9950),
new Edge(pad, sfo, 9000),
// from Beijing
new Edge(bjs, sfo, 9510),
// from New York
new Edge(nyc, bjs, 11000),
new Edge(nyc, sfo, 4140),
// from San Francisco
new Edge(sfo, sao, 10400),
// from Sao Paulo
new Edge(sao, nyc, 7680),
//Paderborn incoming
new Edge(nyc, pad, 6130),
new Edge(bjs, pad, 7660),
new Edge(sao, pad, 9950),
new Edge(sfo, pad, 9000),
};
var vehicles = 3; // initialize 3 vehicles
var capacity = 4000; // each vehicle has a capacity of 4000 units
// Use long names for easier debugging/model understanding.
var config = new Configuration();
config.NameHandling = NameHandlingStyle.UniqueLongNames;
config.ComputeRemovedVariables = true;
using (var scope = new ModelScope(config))
{
// create a model, based on given data and the modelscope
var VRPModel = new VehicleRoutingModel(nodes, edges, vehicles, capacity);
// Get a solver instance, change your solver
using (var solver = new GurobiSolver())
{
try
{
// troubleshooting
solver.Configuration.TimeLimit = 1;
(solver.Configuration as GurobiSolverConfiguration).ComputeIIS = true;
// troubleshooting
// solve the model
var solution = solver.Solve(VRPModel.Model);
if (solution.ConflictingSet != null)
{
var conflicts = solution.ConflictingSet.ToString();
Console.WriteLine(conflicts);
}
// import the results back into the model
VRPModel.Model.VariableCollections.ForEach(vc => vc.SetVariableValues(solution.VariableValues));
// print objective and variable decisions
Console.WriteLine($"{solution.ObjectiveValues.Single()}");
VRPModel.x.Variables.ForEach(x => Console.WriteLine($"{x.ToString().PadRight(36)}: {x.Value}"));
VRPModel.y.Variables.ForEach(y => Console.WriteLine($"{y.ToString().PadRight(36)}: {y.Value}"));
VRPModel.Model.VariableStatistics.WriteCSV(AppDomain.CurrentDomain.BaseDirectory);
}
catch (Exception e)
{
Console.WriteLine(e);
}
Console.ReadLine();
}
}
}
}
}
Next Step
- Creating the Model