Задача маршрутизации транспортных средств (VRP) — это сложная оптимизационная задача, заключающаяся в поиске наиболее эффективных маршрутов для парка транспортных средств, доставляющих товары группе клиентов. Несмотря на свою сложность, VRP имеет множество реальных приложений, таких как службы доставки, транспорт и логистика. В этом посте на Medium мы воспользуемся прагматичным и образовательным подходом к решению VRP с использованием TypeScript. Мы предоставим обзор VRP и его ключевых концепций, а затем познакомим вас с нашей реализацией простого эвристического алгоритма. Независимо от того, являетесь ли вы новичком или опытным разработчиком, этот пост предоставит ценную информацию и поможет вам понять VRP и его решения.
История
За прошедшие годы были предложены различные математические модели и алгоритмы для решения VRP, включая, среди прочего, линейное программирование, динамическое программирование и целочисленное программирование. В конце 1990-х метаэвристика, такая как генетические алгоритмы, имитация отжига и оптимизация муравьиной колонии, стала популярной для решения VRP и других задач комбинаторной оптимизации.
Совсем недавно исследователи сосредоточились на разработке гибридных метаэвристик, которые объединяют сильные стороны нескольких методов оптимизации для достижения лучших результатов. Исследователи также изучили использование алгоритмов машинного обучения, таких как нейронные сети и глубокое обучение с подкреплением, для решения VRP. Кроме того, продолжаются исследования по использованию больших данных и облачных вычислений для решения проблем VRP с очень большим количеством клиентов и транспортных средств.
В целом VRP остается активной областью исследований, и регулярно предлагаются новые алгоритмы и подходы. Цель этого исследования — найти эффективные и действенные решения для VRP, которые можно применять в реальных логистических и транспортных приложениях.
Вот три основных подхода, используемых для решения задачи маршрутизации транспортных средств (VRP):
- Метаэвристика. Метаэвристика — это класс алгоритмов оптимизации, которые используют набор эвристик для поиска качественных решений за разумное время. Примеры популярных метаэвристик для VRP включают генетические алгоритмы, моделирование отжига и оптимизацию муравьиной колонии.
- Целочисленное линейное программирование (ILP): ILP – это метод математической оптимизации, используемый для решения задач с двоичными переменными. ILP — это мощный инструмент для VRP, поскольку он может учитывать множество ограничений и целей, таких как вместимость транспортного средства, временные окна и приоритет заказа.
- Генерация столбцов: Генерация столбцов — это метод, используемый для решения крупномасштабных задач линейного программирования путем разложения исходной задачи на более мелкие, более управляемые подзадачи. Генерация столбцов часто используется в сочетании с другими методами оптимизации, такими как ответвления и сокращения или ответвления и цены, для предоставления высококачественных решений проблем VRP.
Эвристические алгоритмы и VRP
Эвристические алгоритмы на дополнительной стороне представляют собой класс алгоритмов, которые используют набор правил и методов для поиска приемлемого решения в разумные сроки, а не для поиска точного и оптимального решения. Эти алгоритмы часто используются для решения сложных задач, в том числе задачи маршрутизации транспортных средств (VRP), где исчерпывающий поиск нецелесообразен с вычислительной точки зрения. Алгоритмы эвристики используют метод проб и ошибок для поиска решения, близкого к оптимальному, на основе доступных данных и информации. Они являются привлекательным вариантом для решения VRP, поскольку позволяют быстро находить решения даже для крупномасштабных проблем, а также их можно адаптировать и улучшать с течением времени по мере поступления новых данных и информации. Эвристические алгоритмы широко используются в области VRP, и они продолжают оставаться активной областью исследований, и многие исследователи изучают новые и инновационные подходы к решению этой сложной проблемы.
Реализация TypeScript VRP
В этой модели VRP мы определили несколько классов для представления проблемы:
Position: представляет географическое положение с координатами широты и долготы.DeliveryOrder: представляет заказ на доставку от клиента, включая идентификатор клиента, мощность, местоположение, идентификатор заказа и дату/время. Он также имеет атрибут веса, который можно использовать для учета внешних факторов, таких как трафик, погода и дорожные условия.Vehicle: представляет транспортное средство доставки, включая его вместимость, текущее положение и идентификатор транспортного средства.DeliveryPlan: представляет собой окончательный оптимизированный план доставки, включая маршруты транспортных средств и любые ожидающие заказы на доставку, которые не могут быть выполнены.
Класс DeliveryService является основным классом, реализующим оптимизацию VRP. Он принимает массив транспортных средств и заказов на доставку в качестве входных данных и возвращает DeliveryPlan в качестве выходных данных.
Алгоритм
Алгоритм в методе optimizeDeliveryPlan использует эвристический подход, что означает, что он использует набор правил и методов для поиска приемлемого решения в разумные сроки вместо поиска точного и оптимального решения. Этот подход полезен при решении задач с большим количеством переменных, когда полный перебор нецелесообразен с вычислительной точки зрения.
Алгоритм сначала сортирует заказы на доставку ASC по «вместимости * весу заказа» (где вес представляет такие условия, как цена, трафик, погода, дорога и т. д.). Затем транспортные средства сортируются по возрастанию расстояния между их текущим положением и местоположением заказа, при этом задачи доставки сначала назначаются транспортным средствам, ближайшим к местоположению заказа.
Затем алгоритм назначает заказы транспортным средствам, перебирая заказы и сравнивая расстояние между каждым транспортным средством и местоположением заказа. Для доставки заказа выбирается транспортное средство с наименьшим общим расстоянием, учитывая как текущее расстояние от транспортного средства до заказа, так и расстояние от последнего заказа до текущего заказа. Вместимость выбранного транспортного средства обновляется, а заказ на доставку добавляется в маршрут транспортного средства.
Этот процесс продолжается до тех пор, пока все заказы не будут назначены транспортным средствам или пока не закончатся транспортные средства для выполнения заказов. Окончательный результат сохраняется в объекте DeliveryPlan, который содержит маршруты для каждого транспортного средства и отложенные заказы, которые не могут быть назначены ни одному транспортному средству.
class VehicleRoutes {
public readonly routes: Map<Vehicle, DeliveryOrder[]> = new Map<Vehicle, DeliveryOrder[]>()
public getVehicleRoute (vehicle: Vehicle): DeliveryOrder[] {
if (!this.routes.has(vehicle)) {
this.routes.set(vehicle, [])
}
return this.routes.get(vehicle) as DeliveryOrder[]
}
public getVehicleLastOrder (vehicle: Vehicle): DeliveryOrder | undefined {
const route = this.getVehicleRoute(vehicle)
return (route.length > 0) ? route[route.length - 1] : undefined
}
}
class DeliveryService {
constructor (
private readonly vehicles: Vehicle[],
private readonly orders: DeliveryOrder[]
) {
}
public optimizeDeliveryPlan (): DeliveryPlan {
// Sort delivery orders ASC by capacity * weight
// (weight = optional placeholder for conditions around Price, Traffic, Weather, Road, etc...)
this.orders.sort((a, b) => a.capacity * a.weight - b.capacity * b.weight)
// Sort vehicles ASC by distance between current position and order location
this.vehicles.sort((a, b) => {
const distanceA = a.currentPosition.distanceTo(this.orders[0].location)
const distanceB = b.currentPosition.distanceTo(this.orders[0].location)
return distanceA - distanceB
})
const routes = new VehicleRoutes()
// Assign delivery orders to vehicles
let orderIndex = 0
for (; orderIndex < this.orders.length; orderIndex++) {
const order = this.orders[orderIndex]
let selectedVehicle: Vehicle | undefined
let minDistance = Infinity
for (const vehicle of this.vehicles) {
if (vehicle.capacity >= order.capacity) {
const currentDistance = vehicle.currentPosition.distanceTo(order.location)
const lastOrder = routes.getVehicleLastOrder(vehicle)
const distanceToOrder = (lastOrder != null)
? lastOrder.location.distanceTo(order.location)
: currentDistance
if (distanceToOrder < minDistance) {
selectedVehicle = vehicle
minDistance = distanceToOrder
}
}
}
if (selectedVehicle == null) {
break
}
selectedVehicle.capacity = selectedVehicle.capacity - order.capacity
selectedVehicle.currentPosition = order.location
const route = routes.getVehicleRoute(selectedVehicle)
route.push(order)
}
return new DeliveryPlan(routes.routes, this.orders.splice(orderIndex))
}
}
Полная реализация проекта доступна по адресу: https://github.com/jkyberneees/vrp, дайте мне знать ваш отзыв в виде комментария, проблемы GitHub или звездочки 🙏
Демо
import { DeliveryService, generateGeoJsonRoute } from './../libs/vrp'
import { Vehicle, Position, DeliveryOrder } from './../libs/model'
import { FeatureCollection } from 'geojson'
// Mock 5 vehicles around Berlin Kudam
const vehicles = [
new Vehicle('Vehicle1', 100, new Position(52.5075, 13.3295)),
new Vehicle('Vehicle2', 120, new Position(52.5065, 13.3299)),
new Vehicle('Vehicle3', 80, new Position(52.5057, 13.3304)),
new Vehicle('Vehicle4', 90, new Position(52.5055, 13.3307)),
new Vehicle('Vehicle5', 110, new Position(52.5047, 13.3311))
]
let totalVehicleCapacity = 0
vehicles.forEach(vehicle => {
totalVehicleCapacity += vehicle.capacity
})
const orders = []
let totalCapacity = 0
let orderId = 1
// Mock 100 DeliveryOrder objects around Berlin Kudam
while (orders.length < 100 && totalCapacity < totalVehicleCapacity) {
const capacity = Math.floor(Math.random() * 20) + 1
totalCapacity += capacity
if (totalCapacity <= totalVehicleCapacity) {
const longitude = 52.5076 + (Math.random() - 0.5) * 0.01
const latitude = 13.3299 + (Math.random() - 0.5) * 0.01
orders.push(
new DeliveryOrder(
`C${orderId}`,
`Order${orderId}`,
capacity,
new Position(longitude, latitude),
new Date()
)
)
orderId++
}
}
const deliveryService = new DeliveryService(vehicles, orders)
const deliveryPlan = deliveryService.optimizeDeliveryPlan()
console.log(`Pending orders: ${deliveryPlan.pendingOrders.length}`)
console.log('---------------------------')
const routes = deliveryPlan.vehicleRoutes
routes.forEach((route, vehicle) => {
console.log(`Vehicle ID: ${vehicle.driverId}`)
console.log(`Remaining vehicle capacity: ${vehicle.capacity}`)
console.log(`Vehicle position after route: (${vehicle.currentPosition.latitude}, ${vehicle.currentPosition.longitude})`)
console.log('Route:')
const featureCollection: FeatureCollection = generateGeoJsonRoute(route.map(route => route.location))
console.log(JSON.stringify(featureCollection, null, 2))
console.log('---------------------------')
})
Выход:
% time bun demos/basic.ts
Pending orders: 1
---------------------------
Vehicle ID: Vehicle1
Remaining vehicle capacity: 4
Vehicle position after route: (52.50583034392092, 13.33487304674146)
Route:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[
13.32991337766046,
52.51034749703221
],
[
13.326686424912493,
52.51034920018753
],
[
13.329485050516322,
52.510093428426224
],
[
13.32628607773217,
52.50973458196201
],
[
13.33403726888709,
52.51205711618895
],
[
13.334879511915826,
52.5103378908694
],
[
13.332391475570132,
52.509951500211706
],
[
13.329234893876055,
52.510733066267846
],
[
13.328660512426392,
52.511833739904965
],
[
13.331454763227331,
52.51173669284479
],
[
13.33487304674146,
52.50583034392092
]
]
}
}
]
}
---------------------------
Vehicle ID: Vehicle2
Remaining vehicle capacity: 9
Vehicle position after route: (52.5063698629541, 13.329322007200192)
Route:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[
13.326426047309797,
52.510440065872686
],
[
13.330706637328312,
52.509267195367215
],
[
13.326181970858418,
52.5099024454753
],
[
13.32689806191398,
52.5092297820826
],
[
13.325051616688148,
52.510381088184104
],
[
13.325999812207886,
52.50966080779991
],
[
13.329461364176622,
52.51069893085339
],
[
13.32546004859602,
52.51139898626819
],
[
13.325642355963826,
52.51196930630478
],
[
13.326725267395867,
52.510105607170445
],
[
13.329322007200192,
52.5063698629541
]
]
}
}
]
}
---------------------------
Vehicle ID: Vehicle3
Remaining vehicle capacity: 4
Vehicle position after route: (52.50591931839329, 13.329637703132038)
Route:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[
13.326882757181451,
52.504763906426795
],
[
13.326899255875508,
52.50498558326541
],
[
13.32519300845387,
52.50332010156658
],
[
13.326075337659793,
52.50455699877068
],
[
13.328288699765611,
52.5029061043246
],
[
13.326111308110344,
52.50447276487308
],
[
13.327809876539947,
52.505148328946994
],
[
13.324920669211092,
52.50609871688409
],
[
13.327204856312157,
52.50739727470655
],
[
13.326045402201355,
52.50564293812937
],
[
13.329637703132038,
52.50591931839329
]
]
}
}
]
}
---------------------------
Vehicle ID: Vehicle4
Remaining vehicle capacity: 9
Vehicle position after route: (52.50262894639542, 13.331599573142837)
Route:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[
13.330308736865534,
52.50504265774927
],
[
13.328098419280925,
52.50528865358484
],
[
13.330970164975586,
52.504618822039085
],
[
13.330413519327463,
52.50575204033206
],
[
13.332082841544674,
52.50369254870328
],
[
13.3274946829787,
52.50558451357059
],
[
13.334078372367218,
52.50387698723042
],
[
13.331599573142837,
52.50262894639542
]
]
}
}
]
}
---------------------------
Vehicle ID: Vehicle5
Remaining vehicle capacity: 1
Vehicle position after route: (52.50691793951064, 13.333447768161468)
Route:
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[
13.33407946635177,
52.50481306081307
],
[
13.332805946758986,
52.506696502901626
],
[
13.333419027267134,
52.507721585753316
],
[
13.333500859976327,
52.50760438278303
],
[
13.33148312808766,
52.50756990797808
],
[
13.332174233192589,
52.50935113715304
],
[
13.334488053576921,
52.50544422740557
],
[
13.327831741022099,
52.50430154187137
],
[
13.333447768161468,
52.50691793951064
]
]
}
}
]
}
---------------------------
bun demos/basic.ts 0.01s user 0.01s system 94% cpu 0.024 total
Выводы
VRP представляет собой сложную оптимизационную задачу с широким спектром приложений. Хотя существует несколько подходов к решению VRP, эвристические алгоритмы обеспечивают практическое и эффективное решение для поиска приемлемых решений за разумное время. Модель, представленная в этой статье, представляет собой простой и обучающий подход к VRP с использованием TypeScript, и ее можно легко адаптировать и улучшить для более продвинутых вариантов использования. Эта модель является отправной точкой для тех, кто заинтересован в изучении VRP и эвристических алгоритмов, и может использоваться для экспериментов и построения более сложных задач VRP.
Полный исходный код проекта доступен по адресу: https://github.com/jkyberneees/vrp
