Capacitated arc routing problem
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಕೆಪ್ಯಾಸಿಟೆಡ್ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಪ್ರಾಬ್ಲಮ್ (ಸಿಎಆರ್ಪಿ) ಎಂದರೆ, ನಿರ್ದೇಶಿಸದ ಅಂಚುಗಳು ಮತ್ತು ನಿರ್ದೇಶಿತ ಆರ್ಕ್ಗಳೊಂದಿಗೆ ಮಿಶ್ರ ಗ್ರಾಫ್ನ ಕನಿಷ್ಠ ಗ್ರಾಫ್/ಪ್ರಯಾಣದ ದೂರದೊಂದಿಗೆ ಕಡಿಮೆ ಪ್ರವಾಸವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಇದು ಹಿಮ-ಪ್ಲವರ್ಸ್, ಸ್ಟ್ರೀಟ್ ಸ್ವೀಪಿಂಗ್ ಯಂತ್ರಗಳು, ಅಥವಾ ಚಳಿಗಾಲದ ಗ್ರಿಟ್ಟರ್ಗಳು ಅಥವಾ ಸಾಮರ್ಥ್ಯದ ನಿರ್ಬಂಧಗಳನ್ನು ಹೊಂದಿರುವ ಇತರ ನೈಜ-ಪ್ರಪಂಚದ ವಸ್ತುಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಗ್ರಾಫ್ನ ಉದ್ದಕ್ಕೂ ಚಲಿಸುವ ವಸ್ತುಗಳಿಗೆ ಸಾಮರ್ಥ್ಯದ ನಿರ್ಬಂಧಗಳನ್ನು ನೀಡುತ್ತದೆ. ವಾಹನವು ಕೇಂದ್ರ ಡಿಪೋದಿಂದ ಎಷ್ಟು ದೂರದಲ್ಲಿದೆ, ಅಥವಾ ಪ್ರಯಾಣಿಸಿದ ಒಟ್ಟು ದೂರ, ಅಥವಾ ವಿಭಿನ್ನ ತೂಕದ ಅಂಶಗಳೊಂದಿಗೆ ಇವೆರಡರ ಸಂಯೋಜನೆಗೆ ನಿರ್ಬಂಧವನ್ನು ವಿಧಿಸಬಹುದು. ಏಂಜೆಲ್ ಕಾರ್ಬೆರಾನ್ ಮತ್ತು ಗಿಲ್ಬರ್ಟ್ ಲ್ಯಾಪೋರ್ಟೆ ಅವರ ಆರ್ಕ್ ರೂಟಿಂಗ್ಃ ಪ್ರಾಬ್ಲಮ್ಸ್, ಮೆಥಡ್ಸ್, ಅಂಡ್ ಅಪ್ಲಿಕೇಷನ್ಸ್ ಎಂಬ ಪುಸ್ತಕದಲ್ಲಿ ವಿವರಿಸಲಾದ ಸಿಎಆರ್ಪಿಯ ಅನೇಕ ವಿಭಿನ್ನ ರೂಪಾಂತರಗಳಿವೆ. ಸಿಎಆರ್ಪಿ ಅನ್ನು ಪರಿಹರಿಸುವುದು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ, ಆರ್ಕ್ ರೂಟಿಂಗ್, ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಶೋಧನೆ ಮತ್ತು ಭೌಗೋಳಿಕ ರೂಟಿಂಗ್ ಕ್ರಮಾವಳಿಗಳ ಅಧ್ಯಯನವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಸಿಎಆರ್ಪಿ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಿಎಆರ್ಪಿ ಅನ್ನು ಕನ್ವೆಕ್ಸ್ ಹಲ್ಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ನೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದು. ದೊಡ್ಡ-ಪ್ರಮಾಣದ ಕೆಪ್ಯಾಸಿಟೆಡ್ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಯು (ಎಲ್ಎಸ್ಸಿಎಆರ್ಪಿ) ಕೆಪ್ಯಾಸಿಟೆಡ್ ಆರ್ಕ್ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಯ ಒಂದು ರೂಪಾಂತರವಾಗಿದ್ದು, ಇದು ನೂರಾರು ಅಂಚುಗಳು ಮತ್ತು ನೋಡ್ಗಳಿಗೆ ಅನ್ವಯಿಸುತ್ತದೆ ಮತ್ತು ದೊಡ್ಡ ಸಂಕೀರ್ಣ ಪರಿಸರಗಳನ್ನು ವಾಸ್ತವಿಕವಾಗಿ ಅನುಕರಿಸುತ್ತದೆ ಮತ್ತು ರೂಪಿಸುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ