En effektiv ruttplanering för eldrivna fordonsflottor (ECV) måste ta hänsyn till deras begränsade autonomi och möjligheten att besöka laddningsstationer under en rutt. I detta papper anser vi att fyra varianter av det elektriska fordons-routing problemet med tidsfönster: (i) högst en laddning per rutt är tillåtet, och batterier är helt laddade vid besök av en laddningsstation, (ii) flera laddningar per rutt, endast full laddning, (iii) högst en enda laddning per rutt, och partiella batteriladdningar är möjliga, och (iv) flera, partiella laddningar. För varje variant presenterar vi exakta grenpris-och-cut-algoritmer som är beroende av anpassade enkelriktade och dubbelriktade märkningsalgoritmer för att generera genomförbara fordonsrutter. I beräkningsstudier finner vi att alla fyra varianterna kan lösas för fall med upp till 100 kunder och 21 laddningsstationer. Denna framgång kan tillskrivas de skräddarsydda resursförlängningsfunktionerna (Referenser) som möjliggör effektiv märkning med kontinuerlig kontroll av genomförbarheten och starka dominansregler, även om dessa REF-dokument är invecklade och ganska detaljerade att härleda. Studierna belyser också överlägsenheten hos de dubbelriktade märkningsalgoritmerna jämfört med de enkelriktade algoritmerna. Slutligen finner vi att tillåta flera såväl som partiella laddningar både bidrar till att minska routing kostnader och antalet anställda fordon i jämförelse med varianterna med enstaka och med full laddningar.
REF föreslog en gren-och-klipp-och-pris algoritm för detta problem, med en dubbelriktad märkning algoritm för fullständig och partiell laddning på enstaka eller flera laddningsstationer.
Exact algorithms for electric vehicle-routing problems with time windows
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}