Khwaja Fareed University of Engineering &
Information Technology Rahim Yar Khan
NAME: _______________________
REG NO: ______________________
// RoutePlanningAlgorithm.h
#ifndef ROUTE_PLANNING_ALGORITHM_H
#define ROUTE_PLANNING_ALGORITHM_H
#include <vector>
#include <queue>
#include <unordered_map>
#include <utility>
struct Node {
int id;
double x, y; // coordinates
};
struct Edge {
int from, to;
double distance;
};
struct Delivery {
int locationId;
int timeWindowStart, timeWindowEnd;
};
class RoutePlanningAlgorithm {
public:
RoutePlanningAlgorithm(const std::vector<Node>& nodes, const std::vector<Edge>& edges);
void addDelivery(const Delivery& delivery);
void optimizeRoutes();
std::vector<std::vector<int>> getRoutes() const;
private:
std::vector<Node> nodes_;
std::vector<Edge> edges_;
std::vector<Delivery> deliveries_;
std::vector<std::vector<int>> routes_;
// Dijkstra's algorithm implementation
std::vector<double> dijkstra(int startNode) const;
// Nearest Neighbor Insertion heuristic
void nearestNeighborInsertion();
// Simulated Annealing optimization
void simulatedAnnealing();
};
#endif // ROUTE_PLANNING_ALGORITHM_H
// [Link]
#include "RoutePlanningAlgorithm.h"
#include <algorithm>
#include <cmath>
#include <limits>
RoutePlanningAlgorithm::RoutePlanningAlgorithm(const std::vector<Node>& nodes, const
std::vector<Edge>& edges)
: nodes_(nodes), edges_(edges) {}
void RoutePlanningAlgorithm::addDelivery(const Delivery& delivery) {
deliveries_.push_back(delivery);
void RoutePlanningAlgorithm::optimizeRoutes() {
// Initialize routes with a single node (depot)
routes_.resize(deliveries_.size());
for (int i = 0; i < deliveries_.size(); ++i) {
routes_[i].push_back(0); // depot node
// Apply Nearest Neighbor Insertion heuristic
nearestNeighborInsertion();
// Apply Simulated Annealing optimization
simulatedAnnealing();
}
std::vector<std::vector<int>> RoutePlanningAlgorithm::getRoutes() const {
return routes_;
std::vector<double> RoutePlanningAlgorithm::dijkstra(int startNode) const {
std::vector<double> distances(nodes_.size(), std::numeric_limits<double>::infinity());
distances[startNode] = 0;
std::priority_queue<std::pair<double, int>> pq;
[Link]({0, startNode});
while (![Link]()) {
int currentNode = [Link]().second;
[Link]();
for (const Edge& edge : edges_) {
if ([Link] == currentNode) {
int neighbor = [Link];
double distance = [Link] + distances[currentNode];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
[Link]({distance, neighbor});
return distances;
}
void RoutePlanningAlgorithm::nearestNeighborInsertion() {
for (int i = 0; i < deliveries_.size(); ++i) {
int currentNode = routes_[i].back();
int nearestNeighbor = -1;
double minDistance = std::numeric_limits<double>::infinity();
for (int j = 0; j < deliveries_.size(); ++j) {
if (i != j) {
int neighbor = deliveries_[j].locationId;
double distance = dijkstra(currentNode)[neighbor];
if (distance < minDistance) {
minDistance = distance;
nearestNeighbor = neighbor;
routes_[i].push_back(nearestNeighbor);
void RoutePlanningAlgorithm::simulatedAnnealing() {
// TO DO: implement Simulated Annealing optimization
// This is a placeholder, you need to implement the actual algorithm
1. Use a more efficient data structure for the graph: The current
implementation uses a vector of edges, which can lead to slow query times. Consider
using an adjacency list or a more advanced graph data structure like a Fibonacci heap.
2. Implement a more efficient shortest path algorithm: Dijkstra's algorithm
has a time complexity of O(|E| + |V|log|V|), which can be slow for large graphs.
Consider using A* search or a more advanced algorithm like Yen's k-Shortest Paths.
3. Use a more efficient heuristic for route optimization : The Nearest
Neighbor Insertion heuristic is simple but may not produce optimal results. Consider
using more advanced heuristics like Christofides algorithm or Genetic Algorithms.
4. Implement a more efficient optimization algorithm: Simulated Annealing
is a good starting point, but you may want to consider more advanced optimization
algorithms like Ant Colony Optimization or Particle Swarm Optimization.