Vehicle Routing Problem (VRP) Solver
Example solving Vehicle Routing Problem (VRP) using MapVina GL API.
<!DOCTYPE html>
<html>
<head>
<title>Vehicle Routing Problem (VRP) Solver</title>
<meta property="og:description" content="Example solving Vehicle Routing Problem (VRP) using MapVina GL API." />
<meta charset="utf-8" />
<meta name="viewport" content="initial-scale=1,maximum-scale=1,user-scalable=no" />
<script src="https://unpkg.com/[email protected]/dist/mapvina-gl.js"></script>
<link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/mapvina-gl.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/mapbox-polyline/1.2.1/polyline.js"></script>
<link rel="stylesheet" href="/assets/vrp-style.css" />
<script src="/assets/vrp-data.js"></script>
</head>
<body>
<div id="map"></div>
<div id="sidebar">
<section class="section active">
<h3>Input</h3>
<div class="file-input-container">
<input type="file" id="file" accept="application/json,.json" />
<a class="download-link" id="example-download">Download Example</a>
</div>
</section>
<section id="vehicles-section" class="section active">
<h3>Vehicles</h3>
<ul id="vehicles-list"></ul>
</section>
<section id="jobs-section" class="section active">
<h3>Jobs</h3>
<ul id="jobs-list"></ul>
</section>
<section id="summary-section" class="section">
<h3>Summary</h3>
<ul id="summary-list"></ul>
</section>
<section id="routes-section" class="section">
<h3>Routes</h3>
<ul id="routes-list"></ul>
</section>
<section id="unassigned-section" class="section">
<h3>Unassigned</h3>
<ul id="unassigned-list"></ul>
</section>
</div>
<script>
class VRPSolver {
constructor() {
this.map = null;
this.vehicleColors = [
'#2196f3', '#9c27b0', '#009688', '#3f51b5',
'#ffc107', '#ff9800', '#ff5722', '#795548',
'#607d8b', '#4caf50', '#cddc39', '#00bcd4'
];
this.vehicleColorMap = new Map();
this.markers = [];
this.routeLayers = [];
this.init();
}
init() {
this.initMap();
this.bindEvents();
this.loadExample();
}
initMap() {
this.map = new mapvinagl.Map({
container: "map",
style: "https://maps.mapvina.com/styles/v2/streets.json?key=public_key",
center: [101.96, 13.27],
zoom: 5,
});
this.map.on('load', () => {
console.log('Map loaded successfully');
});
}
bindEvents() {
document.getElementById('file').addEventListener('change', (e) => this.handleFileSelect(e));
document.getElementById('example-download').addEventListener('click', (e) => this.downloadExample(e));
}
getExampleData() {
return window.vrpExampleData;
}
loadExample() {
const example = this.getExampleData();
this.solve(example);
}
downloadExample(event) {
event.preventDefault();
const data = JSON.stringify(this.getExampleData(), null, 2);
const blob = new Blob([data], { type: 'application/json' });
const url = URL.createObjectURL(blob);
const link = document.createElement('a');
link.href = url;
link.download = 'vrp-example.json';
document.body.appendChild(link);
link.click();
document.body.removeChild(link);
URL.revokeObjectURL(url);
}
handleFileSelect(event) {
const file = event.target.files[0];
if (!file) return;
const reader = new FileReader();
reader.onload = (e) => {
try {
const data = JSON.parse(e.target.result);
this.clearAll();
this.solve(data);
} catch (error) {
alert('Error parsing JSON file: ' + error.message);
}
};
reader.readAsText(file);
}
clearAll() {
// Clear markers
this.markers.forEach(marker => marker.remove());
this.markers = [];
// Clear route layers
this.routeLayers.forEach(layerId => {
if (this.map.getLayer(layerId)) {
this.map.removeLayer(layerId);
this.map.removeSource(layerId);
}
});
this.routeLayers = [];
this.clearUILists();
this.vehicleColorMap.clear();
this.currentInputData = null;
}
clearUILists() {
const lists = ['vehicles-list', 'jobs-list', 'routes-list', 'unassigned-list', 'summary-list'];
lists.forEach(listId => {
document.getElementById(listId).innerHTML = '';
});
// Hide sections
['summary-section', 'routes-section', 'unassigned-section'].forEach(sectionId => {
document.getElementById(sectionId).classList.remove('active');
});
}
solve(input) {
// Store input data for later use with unassigned jobs
this.currentInputData = input;
const focusPoint = this.getFocusPoint(input);
if (focusPoint) {
this.map.flyTo({
center: focusPoint,
zoom: 10,
speed: 1.5
});
}
// Prepare input for API
const apiInput = { ...input, options: { g: true } };
// Populate UI
if (input.vehicles) this.populateVehicles(input.vehicles);
if (input.shipments) this.populateShipments(input.shipments);
if (input.jobs) this.populateJobs(input.jobs);
// Fetch and display routes
this.fetchRoutes(apiInput);
}
getFocusPoint(input) {
return input.shipments?.[0]?.pickup?.location ||
input.jobs?.[0]?.location ||
input.vehicles?.[0]?.start;
}
populateVehicles(vehicles) {
const vehiclesList = document.getElementById('vehicles-list');
vehicles.forEach((vehicle, index) => {
const color = this.vehicleColors[index % this.vehicleColors.length];
this.vehicleColorMap.set(vehicle.id, color);
const li = document.createElement('li');
const title = vehicle.description || `Vehicle ${vehicle.id}`;
li.innerHTML = `<span style="color: ${color}; font-weight: 500;">${title}</span>`;
vehiclesList.appendChild(li);
});
}
populateShipments(shipments) {
const jobsList = document.getElementById('jobs-list');
shipments.forEach((shipment, index) => {
const shipmentLi = document.createElement('li');
shipmentLi.innerHTML = `<strong>Shipment ${index + 1}</strong>`;
const jobsUl = document.createElement('ul');
jobsUl.style.marginTop = '8px';
const pickupLi = document.createElement('li');
pickupLi.innerHTML = `<span class="text-green">PICKUP ${shipment.pickup.id}:</span> ${shipment.pickup.description}`;
const deliveryLi = document.createElement('li');
deliveryLi.innerHTML = `<span class="text-red">DELIVERY ${shipment.delivery.id}:</span> ${shipment.delivery.description}`;
jobsUl.appendChild(pickupLi);
jobsUl.appendChild(deliveryLi);
shipmentLi.appendChild(jobsUl);
jobsList.appendChild(shipmentLi);
});
}
populateJobs(jobs) {
const jobsList = document.getElementById('jobs-list');
jobs.forEach((job, index) => {
const jobLi = document.createElement('li');
const jobTitle = job.description || `Location: ${job.location.join(', ')}`;
jobLi.innerHTML = `<strong>Job ${index + 1}:</strong> ${jobTitle}`;
jobsList.appendChild(jobLi);
});
}
async fetchRoutes(input) {
try {
const response = await fetch('https://maps.mapvina.com/api/v1/vrp/?key=public_key', {
method: 'POST',
headers: { 'Content-Type': 'application/json' },
body: JSON.stringify(input),
});
if (!response.ok) {
throw new Error(`HTTP error! status: ${response.status}`);
}
const data = await response.json();
this.handleRoutesResponse(data);
} catch (error) {
console.error('API request failed:', error);
alert(`Request failed: ${error.message}`);
}
}
handleRoutesResponse(response) {
if (response.routes?.length > 0) {
this.displayRoutes(response.routes);
document.getElementById('routes-section').classList.add('active');
}
if (response.unassigned?.length > 0) {
this.displayUnassigned(response.unassigned);
this.displayUnassignedMarkers(response.unassigned);
document.getElementById('unassigned-section').classList.add('active');
}
if (response.summary) {
this.displaySummary(response.summary);
document.getElementById('summary-section').classList.add('active');
}
}
displayRoutes(routes) {
const routesList = document.getElementById('routes-list');
routes.forEach(route => {
const vehicleColor = this.vehicleColorMap.get(route.vehicle);
const vehicleTitle = route.description || `Vehicle ${route.vehicle}`;
// Create route geometry
this.createRouteLayer(route, vehicleColor);
// Create route UI
const routeLi = document.createElement('li');
// Route control
const controlDiv = document.createElement('div');
controlDiv.className = 'route-control';
controlDiv.innerHTML = `
<label>
<input type="checkbox"
data-vehicle-id="${route.vehicle}"
checked
onchange="vrpSolver.toggleRoute(this)">
<span style="color: ${vehicleColor};">${vehicleTitle}</span>
</label>
`;
// Route stops
const stopsUl = document.createElement('ul');
this.createRouteStops(route, stopsUl, vehicleColor);
routeLi.appendChild(controlDiv);
routeLi.appendChild(stopsUl);
routesList.appendChild(routeLi);
});
}
createRouteLayer(route, color) {
const routeGeoJSON = polyline.toGeoJSON(route.geometry);
const layerId = `route-${route.vehicle}`;
this.map.addSource(layerId, {
type: 'geojson',
data: routeGeoJSON,
});
this.map.addLayer({
id: layerId,
type: 'line',
source: layerId,
layout: {
'line-join': 'round',
'line-cap': 'round',
},
paint: {
'line-color': color,
'line-width': 4,
'line-opacity': 0.7,
},
});
this.routeLayers.push(layerId);
}
createRouteStops(route, container, vehicleColor) {
const filteredSteps = route.steps.filter(stop => stop.type !== 'break');
filteredSteps.forEach((stop, index) => {
const markerConfig = this.getMarkerConfig(stop, index, vehicleColor);
const marker = this.createMarker(stop, markerConfig, route);
this.markers.push(marker);
// Create stop list item
const stopLi = document.createElement('li');
stopLi.className = 'stop-item';
// Create mini marker for list
const miniMarker = this.createMiniMarker(markerConfig);
const description = this.getStopDescription(stop);
stopLi.appendChild(miniMarker);
stopLi.appendChild(document.createTextNode(description));
container.appendChild(stopLi);
});
}
getMarkerConfig(stop, index, vehicleColor) {
const config = {
symbol: index.toString(),
color: vehicleColor,
size: 'normal',
priority: 1,
opacity: 0.6,
};
switch (stop.type) {
case 'start':
config.symbol = 'A';
config.size = 'large';
config.priority = 0;
config.opacity = 1;
break;
case 'end':
config.symbol = 'B';
config.size = 'large';
config.priority = 0;
config.opacity = 1;
break;
case 'pickup':
config.opacity = 0.8;
config.symbol = '🠱';
break;
case 'delivery':
config.opacity = 0.8;
config.symbol = '🠯';
break;
case 'job':
config.opacity = 0.7;
break;
}
return config;
}
createMarker(stop, config, route) {
const markerElement = this.createMarkerElement(config, route.vehicle);
const marker = new mapvinagl.Marker({ element: markerElement });
marker.setLngLat(stop.location);
marker.setPopup(this.createPopup(route, stop));
marker.addTo(this.map);
return marker;
}
createMarkerElement(config, vehicleId) {
const markerEl = document.createElement('div');
markerEl.innerHTML = `
<div class="custom-marker ${config.size} draw-vehicle-${vehicleId}"
style="background-color: ${config.color}; z-index: ${config.priority}; opacity: ${config.opacity};">
<div class="custom-marker-content">${config.symbol}</div>
</div>
`;
return markerEl;
}
createMiniMarker(config) {
const miniMarker = document.createElement('div');
miniMarker.className = 'stop-marker';
miniMarker.innerHTML = `
<div class="custom-marker small" style="background-color: ${config.color}; opacity: ${config.opacity};">
<div class="custom-marker-content">${config.symbol}</div>
</div>
`;
return miniMarker;
}
getStopDescription(stop) {
let description = stop.type.toUpperCase();
if (stop.id) description += ` ${stop.id}`;
if (stop.description) description += `: ${stop.description}`;
else if (stop.location) description += `: ${stop.location.join(', ')}`;
return description;
}
createPopup(route, stop) {
const vehicleTitle = route.description || `Vehicle ${route.vehicle}`;
let content = `<div class="popup-title">${vehicleTitle}</div>`;
content += `<div><strong>${stop.type.toUpperCase()}</strong>`;
if (stop.id) content += ` ${stop.id}`;
content += '</div>';
Object.entries(stop).forEach(([key, value]) => {
if (['location', 'type', 'id'].includes(key)) return;
let displayValue = value;
if (key === 'arrival') {
displayValue = `${value} (${new Date(value * 1000).toLocaleString()})`;
} else if (['duration', 'setup', 'service', 'waiting_time'].includes(key)) {
displayValue = `${value}s (${(value / 3600).toFixed(2)}h)`;
} else if (key === 'distance') {
displayValue = `${value}m (${(value / 1000).toFixed(2)}km)`;
}
content += `<div class="popup-detail"><strong>${key}:</strong> ${displayValue}</div>`;
});
return new mapvinagl.Popup({
offset: 25,
className: 'custom-popup'
}).setHTML(content);
}
displayUnassigned(unassigned) {
const unassignedList = document.getElementById('unassigned-list');
unassigned.forEach(job => {
const li = document.createElement('li');
// Create mini marker for unassigned job
const miniMarker = document.createElement('div');
miniMarker.className = 'stop-marker';
miniMarker.innerHTML = `
<div class="custom-marker small" style="background-color: #333333; opacity: 1;">
<div class="custom-marker-content">X</div>
</div>
`;
const textSpan = document.createElement('span');
textSpan.innerHTML = `<strong>${job.type.toUpperCase()} ${job.id}:</strong> ${job.description || 'No description'}`;
li.style.display = 'flex';
li.style.alignItems = 'center';
li.style.gap = '8px';
li.appendChild(miniMarker);
li.appendChild(textSpan);
unassignedList.appendChild(li);
});
}
displayUnassignedMarkers(unassigned) {
// Get original input data to find locations for unassigned jobs
const inputData = this.currentInputData;
if (!inputData) return;
unassigned.forEach(unassignedJob => {
let location = null;
let description = '';
// Find location from original input data
if (unassignedJob.type === 'pickup' || unassignedJob.type === 'delivery') {
// Search in shipments
if (inputData.shipments) {
for (const shipment of inputData.shipments) {
if (unassignedJob.type === 'pickup' && shipment.pickup.id === unassignedJob.id) {
location = shipment.pickup.location;
description = shipment.pickup.description || `Pickup ${unassignedJob.id}`;
break;
} else if (unassignedJob.type === 'delivery' && shipment.delivery.id === unassignedJob.id) {
location = shipment.delivery.location;
description = shipment.delivery.description || `Delivery ${unassignedJob.id}`;
break;
}
}
}
} else if (unassignedJob.type === 'job') {
// Search in jobs
if (inputData.jobs) {
const job = inputData.jobs.find(j => j.id === unassignedJob.id);
if (job) {
location = job.location;
description = job.description || `Job ${unassignedJob.id}`;
}
}
}
// Create marker if location found
if (location) {
const markerConfig = {
symbol: 'X',
color: '#333333', // Black color for unassigned
size: 'normal',
priority: 2,
opacity: 1,
};
const markerElement = this.createUnassignedMarkerElement(markerConfig);
const marker = new mapvinagl.Marker({ element: markerElement });
marker.setLngLat(location);
// Create popup for unassigned job
const popup = new mapvinagl.Popup({
offset: 25,
className: 'custom-popup'
}).setHTML(`
<div class="popup-title">Unassigned Job</div>
<div><strong>${unassignedJob.type.toUpperCase()} ${unassignedJob.id}</strong></div>
<div class="popup-detail"><strong>Description:</strong> ${description}</div>
<div class="popup-detail"><strong>Reason:</strong> Could not be assigned to any vehicle</div>
`);
marker.setPopup(popup);
marker.addTo(this.map);
this.markers.push(marker);
}
});
}
createUnassignedMarkerElement(config) {
const markerEl = document.createElement('div');
markerEl.innerHTML = `
<div class="custom-marker ${config.size} unassigned-marker"
style="background-color: ${config.color}; z-index: ${config.priority}; opacity: ${config.opacity}; border: 2px solid #ff0000;">
<div class="custom-marker-content">${config.symbol}</div>
</div>
`;
return markerEl;
}
displaySummary(summary) {
const summaryList = document.getElementById('summary-list');
const durationLi = document.createElement('li');
durationLi.innerHTML = `<strong>Total Duration:</strong> ${(summary.duration / 3600).toFixed(2)} hours`;
const distanceLi = document.createElement('li');
distanceLi.innerHTML = `<strong>Total Distance:</strong> ${(summary.distance / 1000).toFixed(2)} km`;
summaryList.appendChild(durationLi);
summaryList.appendChild(distanceLi);
}
toggleRoute(checkbox) {
const vehicleId = checkbox.getAttribute('data-vehicle-id');
const visibility = checkbox.checked ? 'visible' : 'none';
const markerVisibility = checkbox.checked ? 'visible' : 'hidden';
// Toggle route layer
const layerId = `route-${vehicleId}`;
if (this.map.getLayer(layerId)) {
this.map.setLayoutProperty(layerId, 'visibility', visibility);
}
// Toggle markers for this vehicle
const markers = document.getElementsByClassName(`draw-vehicle-${vehicleId}`);
Array.from(markers).forEach(marker => {
marker.style.visibility = markerVisibility;
});
// Note: Unassigned markers are always visible as they don't belong to any vehicle
}
}
// Initialize the application
const vrpSolver = new VRPSolver();
</script>
</body>
</html>