Vehicle Routing Problem (VRP) Solver
Example solving Vehicle Routing Problem (VRP) using TrackAsia 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 TrackAsia 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/trackasia-gl.js"></script>
<link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/trackasia-gl.css" />
<script src="https://unpkg.com/@trackasia/[email protected]/index.js"></script>
<style>
body {
margin: 0;
padding: 0;
}
html,
body,
#map {
height: 100%;
}
#map {
position: fixed;
top: 0;
bottom: 0;
width: 70%;
}
#sidebar {
width: 30%;
margin-left: 70%;
overflow-y: auto;
background-color: #fafafa;
height: 100vh;
}
/* Component Styles */
.section {
padding: 15px;
border-bottom: 1px solid #ddd;
opacity: 0.25;
font-size: 13px;
line-height: 1.4;
transition: opacity 0.3s ease;
}
.section.active {
opacity: 1;
}
.section h3 {
margin: 0 0 10px 0;
font-size: 16px;
color: #333;
}
.section ul {
margin: 0;
padding: 0;
list-style: none;
}
.section li {
margin: 5px 0;
padding: 5px;
background: white;
border-radius: 4px;
box-shadow: 0 1px 3px rgba(0, 0, 0, 0.1);
}
/* Input Styles */
.file-input-container {
margin: 10px 0;
}
#file {
width: 100%;
padding: 8px;
border: 1px solid #ddd;
border-radius: 4px;
font-size: 12px;
}
.download-link {
color: #1976d2;
cursor: pointer;
text-decoration: underline;
font-size: 12px;
display: inline-block;
margin-top: 8px;
}
.download-link:hover {
color: #1565c0;
}
/* Marker Styles */
.custom-marker {
width: 24px;
height: 24px;
border-radius: 50% 50% 50% 0;
background: orange;
position: relative;
transform: rotate(-45deg);
border: 2px solid white;
box-shadow: 0 2px 4px rgba(0, 0, 0, 0.3);
}
.custom-marker-content {
position: absolute;
top: 50%;
left: 20%;
font-size: 10px;
font-weight: bold;
transform: rotate(45deg) translate(-50%, -50%);
color: white;
text-shadow: 0 1px 2px rgba(0, 0, 0, 0.5);
}
.custom-marker.large {
width: 28px;
height: 28px;
}
.custom-marker.small {
width: 20px;
height: 20px;
}
/* Route Control Styles */
.route-control {
display: flex;
align-items: center;
gap: 8px;
margin-bottom: 10px;
}
.route-control input[type="checkbox"] {
margin: 0;
}
.route-control label {
display: flex;
align-items: center;
gap: 6px;
cursor: pointer;
font-weight: 500;
}
/* Stop List Styles */
.stop-item {
display: flex;
align-items: center;
gap: 8px;
padding: 6px;
font-size: 11px;
}
.stop-marker {
position: static !important;
transform: none !important;
flex-shrink: 0;
}
/* Popup Styles */
.custom-popup .trackasiagl-popup-content {
padding: 12px;
max-width: 600px;
max-height: 200px;
overflow: scroll;
}
.popup-title {
margin: 0 0 8px 0;
font-size: 14px;
font-weight: bold;
color: #333;
}
.popup-detail {
margin: 4px 0;
font-size: 12px;
color: #666;
}
/* Utility Classes */
.text-green {
color: #4caf50;
}
.text-red {
color: #f44336;
}
.text-blue {
color: #2196f3;
}
.text-purple {
color: #9c27b0;
}
.text-orange {
color: #ff9800;
}
/* Loading State */
.loading {
display: inline-block;
width: 16px;
height: 16px;
border: 2px solid #f3f3f3;
border-top: 2px solid #333;
border-radius: 50%;
animation: spin 1s linear infinite;
}
@keyframes spin {
0% {
transform: rotate(0deg);
}
100% {
transform: rotate(360deg);
}
}
</style>
</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 trackasiagl.Map({
container: "map",
style: "https://maps.track-asia.com/styles/v1/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 {
vehicles: [
{
id: 1,
description: "Van 1",
start: [106.6177357, 10.7409972],
end: [106.5983012, 10.8879148],
profile: "car",
time_window: [1685953800, 1686418200],
skills: [1, 7000],
capacity: [5],
},
{
id: 2,
description: "Van 2",
start: [106.6177357, 10.7409972],
end: [106.7079045, 10.8152603],
profile: "car",
time_window: [1685953800, 1686418200],
skills: [1, 7000],
breaks: [
{
id: 1000,
time_windows: [[1685966400, 1685970000]],
service: 3600,
},
{
id: 1,
time_windows: [[1685986200, 1685988000]],
service: 54000,
},
],
capacity: [10],
},
{
id: 3,
description: "Truck 1",
start: [106.620553, 10.729023],
profile: "car",
time_window: [1685953800, 1686418200],
skills: [1, 1000],
speed_factor: 0.6,
capacity: [20],
},
],
shipments: [
{
amount: [1],
pickup: {
id: 51,
service: 60,
location: [106.765406, 10.744242],
description: "Can not pickup",
time_windows: [[1685986200, 1685988000]],
},
delivery: {
id: 51,
service: 300,
location: [106.712753, 10.784523],
description: "Can not delivery",
time_windows: [
[1685948400, 1685980800],
],
},
skills: [1],
},
{
amount: [1],
pickup: {
id: 1,
service: 60,
location: [106.655077, 10.750909],
description: "Chợ Kim Biên, 26/4 Hẻm 24 Trang Tử, Phường 13, Quận 5, Thành phố Hồ Chí Minh",
time_windows: [[1685986200, 1685988000]],
},
delivery: {
id: 1,
service: 300,
location: [106.682258, 10.759913],
description: "Trường Đại Học Sài Gòn, 273 An Dương Vương, Phường 3, Quận 5, Thành phố Hồ Chí Minh",
time_windows: [
[1685948400, 1685980800],
[1686034800, 1686067200],
[1686121200, 1686153600],
[1686207600, 1686240000],
[1686294000, 1686326400],
[1686380400, 1686412800],
],
},
skills: [1],
},
{
amount: [1],
pickup: {
id: 2,
service: 60,
location: [106.655077, 10.750909],
description: "Chợ Kim Biên, 26/4 Hẻm 24 Trang Tử, Phường 13, Quận 5, Thành phố Hồ Chí Minh",
time_windows: [[1685986200, 1685988000]],
},
delivery: {
id: 2,
service: 300,
location: [106.713724, 10.722809],
description: "Crescent Mall, 101 Đường Tôn Dật Tiên, Phường Tân Phong, Quận 7, Thành phố Hồ Chí Minh",
time_windows: [
[1685948400, 1685980800],
[1686034800, 1686067200],
[1686121200, 1686153600],
[1686207600, 1686240000],
[1686294000, 1686326400],
[1686380400, 1686412800],
],
},
skills: [1000],
},
{
amount: [1],
pickup: {
id: 3,
service: 60,
location: [106.661068, 10.757621],
description: "Hùng Vương Plaza, 130 Đường Hồng Bàng, Phường 12, Quận 5, Thành phố Hồ Chí Minh",
time_windows: [[1685953800, 1686253800]],
},
delivery: {
id: 3,
service: 300,
location: [106.704779, 10.786424],
description: "Tòa Nhà Petrolimex, 1 Lê Duẩn, Phường Bến Nghé, Quận 1, Thành phố Hồ Chí Minh",
time_windows: [[1685953800, 1686418200]],
},
skills: [7000],
},
],
};
}
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 = [];
// Clear UI lists
this.clearUILists();
// Reset color map
this.vehicleColorMap.clear();
// Clear stored input data
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.track-asia.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.decodeToGeoJSON(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 trackasiagl.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 trackasiagl.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 trackasiagl.Marker({ element: markerElement });
marker.setLngLat(location);
// Create popup for unassigned job
const popup = new trackasiagl.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>